پیچیدگی زمانی حلقه‌های for و while

1. پیچیدگی زمانی چیست؟

پیچیدگی زمانی (Time Complexity) یعنی الگوریتم شما برای حل یک مسئله در بدترین حالت (یا حالت میانگین)، چند مرحله یا عملیات انجام می‌دهد، نسبت به ورودی با اندازه n.

---

2. حلقه‌های for یا while ساده

مثال ۱:

for i in range(n):

    print(i)

در اینجا حلقه n بار اجرا می‌شود، پس پیچیدگی زمانی:

> O(n)

---

مثال ۲:

i = 1

while i < n:

    i *= 2

در اینجا i هر بار دو برابر می‌شود:

1, 2, 4, 8, ..., n → تعداد دفعات: log₂(n)

پس:

> O(log n)

---

3. حلقه‌های تو در تو (nested loops)

مثال ۳:

for i in range(n):

    for j in range(n):

        print(i, j)

حلقه داخلی برای هر بار اجرای حلقه بیرونی n بار اجرا می‌شود.

پس کل اجرا:

> O(n × n) = O(n²)

---

مثال ۴:

for i in range(n):

    for j in range(i):

        print(i, j)

تعداد کل اجراها: 1 + 2 + 3 + ... + (n-1)

که برابر است با:

> O(n²)

---

4. ترکیب حلقه‌ها (تو در تو vs پشت سر هم)

مثال ۵:

for i in range(n):        # O(n)

    do_something()

for j in range(n):        # O(n)

    do_something_else()

جمع می‌شود:

> O(n) + O(n) = O(n)

(در Big O، ضرایب حذف می‌شوند.)