چرا شمارش دقیق گامها ابزار درستی نیست
تحلیل یک الگوریتم با شمارش تعداد دقیق عملیاتهای پایه آن، همانطور که پیشتر در این مجموعه درباره insertion sort بحث شد، عباراتی تولید میکند که دقیق اما دستوپاگیر هستند، و به جزئیات پیادهسازی، مانند زبان برنامهنویسی و سختافزار، وابستهاند که هیچ ربطی به کارایی بنیادین الگوریتم ندارند. Asymptotic Notation (نمادگذاری مجانبی) این را با توصیف اینکه زمان اجرای یک الگوریتم چگونه با بزرگشدن دلخواه اندازه ورودی رشد میکند حل میکند، و فاکتورهای ثابت و جملههای مرتبهپایینتر که در مقیاس بزرگ ناچیز میشوند را نادیده میگیرد.
نمادگذاری Big-O: یک کران بالای مجانبی
O-notation (خواندهشده "بیگ-اُ") یک کران بالای مجانبی روی نرخ رشد یک تابع را توصیف میکند. بهطور رسمی، برای یک تابع f(n)، مینویسیم f(n) = O(g(n)) اگر ثابتهای مثبت c و n₀ وجود داشته باشند بهگونهای که:
0 ≤ f(n) ≤ c · g(n) برای همه n ≥ n₀به زبان ساده، این یعنی فراتر از یک نقطه مشخص n₀، تابع f(n) هرگز از یک مضرب ثابت g(n) فراتر نمیرود. Big-O یک کران بالا میدهد، پس گفتن اینکه یک الگوریتم در زمان O(n²) اجرا میشود یعنی هرگز از نظر مجانبی بیش از زمان درجهدوم نمیگیرد، هرچند ممکن است کمتر بگیرد.
بهعنوان یک مثال کارشده، اثبات اینکه f(n) = 3n² + 2n + 5 برابر O(n²) است را در نظر بگیرید. باید ثابتهای c و n₀ای پیدا کنیم که تعریف را برآورده کنند.
3n² + 2n + 5 ≤ 3n² + 2n² + 5n² (برای n ≥ 1، چون n ≤ n² و 1 ≤ n²)
= 10n²
پس انتخاب c = 10 و n₀ = 1 برآورده میکند:
3n² + 2n + 5 ≤ 10n² برای همه n ≥ 1
بنابراین، 3n² + 2n + 5 = O(n²)نمادگذاری Big-Omega: یک کران پایین مجانبی
Ω-notation (خواندهشده "بیگ-اُمگا") یک کران پایین مجانبی، تصویر آینهای Big-O، را توصیف میکند. مینویسیم f(n) = Ω(g(n)) اگر ثابتهای مثبت c و n₀ وجود داشته باشند بهگونهای که:
0 ≤ c · g(n) ≤ f(n) برای همه n ≥ n₀این یعنی f(n) حداقل بهاندازه یک مضرب ثابت g(n) فراتر از یک نقطه مشخص رشد میکند. گفتن اینکه یک الگوریتم در زمان Ω(n log n) اجرا میشود یعنی همیشه از نظر مجانبی حداقل آنقدر زمان میگیرد، صرفنظر از اینکه چقدر ماهرانه پیادهسازی شده — این اغلب برای ایجاد کرانهای پایین بنیادین روی کل دستههای الگوریتم استفاده میشود، مانند اثبات اینکه مرتبسازی مبتنی بر مقایسه در بدترین حالت حداقل به Ω(n log n) مقایسه نیاز دارد.
نمادگذاری Big-Theta: یک کران مجانبی محکم
Θ-notation (خواندهشده "بیگ-تتا") یک کران محکم را توصیف میکند: تابعی که همزمان هم O(g(n)) و هم Ω(g(n)) است. بهطور رسمی، f(n) = Θ(g(n)) اگر ثابتهای مثبت c₁، c₂، و n₀ وجود داشته باشند بهگونهای که:
0 ≤ c₁ · g(n) ≤ f(n) ≤ c₂ · g(n) برای همه n ≥ n₀این یعنی f(n) بین دو مضرب ثابت g(n) برای n بهاندازه کافی بزرگ محصور شده است. نمادگذاری تتا دقیقترین توصیف مجانبی را میدهد: گفتن اینکه زمان اجرای یک الگوریتم Θ(n²) است یعنی دقیقاً متناسب با n² رشد میکند، نه سریعتر و نه کندتر از نظر مجانبی.
یک قضیه مهم هر سه نمادگذاری را متصل میکند: f(n) = Θ(g(n)) اگر و فقط اگر f(n) = O(g(n)) و f(n) = Ω(g(n)). این یعنی اثبات یک کران محکم همیشه میتواند با ایجاد جداگانه یک کران بالا و یک کران پایین انجام شود.
یک مقایسه عملی از سه نمادگذاری
O(g(n)) — "با نرخی کمتر از g(n) رشد نمیکند" — کران بالا
Ω(g(n)) — "حداقل بهاندازه g(n) رشد میکند" — کران پایین
Θ(g(n)) — "دقیقاً با نرخ g(n) رشد میکند" — کران محکم
مثال با f(n) = 3n² + 2n + 5:
f(n) = O(n³) — درست، اما محکم نیست (n³ سریعتر رشد میکند)
f(n) = O(n²) — درست و محکم
f(n) = Θ(n²) — درست، توصیف دقیق
f(n) = Ω(n) — درست، اما محکم نیست
f(n) = Ω(n²) — درست و محکمنمادگذاریهای مرتبط اضافه: o و ω
دو نمادگذاری بیشتر، کرانهای سختگیرانه و غیرمحکم را بیان میکنند. o-notation (کوچک-او) یک کران بالا را توصیف میکند که از نظر مجانبی محکم نیست: f(n) = o(g(n)) یعنی f(n) در مقایسه با g(n) با رشد n ناچیز میشود، بهطور رسمی برای هر ثابت مثبت c، یک n₀ وجود دارد بهگونهای که f(n) < c · g(n) برای همه n ≥ n₀. بهطور مشابه، ω-notation (کوچک-اُمگا) یک کران پایین سختگیرانه را توصیف میکند. اینها کمتر از O، Ω، و Θ استفاده میشوند اما گاهی برای مقایسه دقیق نرخهای رشدی که بهطور بنیادین متفاوتاند مفیدند.
نرخهای رشد رایج، از سریعترین تا کندترین
زمانهای اجرای الگوریتم در تعداد کمی دسته رایج نرخ رشد قرار میگیرند، که هر برنامهنویسی باید بتواند آنها را بشناسد و بر اساس سرعت نسبی برای ورودیهای بزرگ مرتب کند.
مرتبشده از سریعترین-رشد (بدترین) تا کندترین-رشد (بهترین):
O(n!) فاکتوریلی — مسائل جایگشت بهروش brute-force
O(2ⁿ) نمایی — جستجوی جامع در سراسر زیرمجموعهها
O(n³) مکعبی — ضرب ماتریس ساده
O(n²) درجهدوم — insertion sort، bubble sort
O(n log n) خطیلگاریتمی — merge sort، heapsort، مرتبسازی کارآمد
O(n) خطی — یک عبور واحد از میان ورودی
O(log n) لگاریتمی — جستجوی دودویی
O(1) ثابت — جستجوی جدول هش (حالت میانگین)یک بینش حیاتی برای درونیکردن این است که این نرخها با رشد n چقدر بهطور چشمگیری از هم واگرا میشوند. برای یک ورودی بهاندازه یک میلیون، یک الگوریتم O(n) تقریباً یک میلیون عملیات انجام میدهد، در حالی که یک الگوریتم O(n²) تقریباً یک تریلیون عملیات انجام میدهد — تفاوتی که یک کار را از آنی به عملاً غیرممکن روی همان سختافزار تبدیل میکند.
ویژگیهایی که نمادگذاری مجانبی را برای اثباتها مفید میکنند
نمادگذاری مجانبی از چند ویژگی ریاضی مفید پیروی میکند که تحلیل را ساده میکنند.
Transitivity(تعدی): اگرf(n) = O(g(n))وg(n) = O(h(n))، آنگاهf(n) = O(h(n)). این برای Ω و Θ نیز برقرار است.Reflexivity(بازتابندگی):f(n) = O(f(n))، و بهطور مشابه برای Ω و Θ.Symmetry(تقارن):f(n) = Θ(g(n))اگر و فقط اگرg(n) = Θ(f(n)). توجه کنید این تقارن برای O و Ω بهطور جداگانه برقرار نیست.Transpose Symmetry(تقارن جابهجایی):f(n) = O(g(n))اگر و فقط اگرg(n) = Ω(f(n))، که رابطه شهودی که O و Ω تصاویر آینهای یکدیگرند را رسمی میکند.
چرا تسلط بر این نمادگذاری ضروری است
هر الگوریتمی که در باقی این مجموعه تحلیل میشود با استفاده از این نمادگذاریها توصیف خواهد شد، تقریباً همیشه Θ وقتی یک توصیف محکم شناختهشده باشد، یا O وقتی فقط یک کران بالا ایجاد شده باشد. تسلط بر این تعاریف — توانایی هم تفسیر یک کران بیانشده و هم اثبات یکی مستقیماً از تعریف رسمی هنگام نیاز — پیشنیازی برای درک، مقایسه، و در نهایت طراحی الگوریتمهای کارآمد است.