نماد O بزرگ؛ زمانی که پای عملکرد الگوریتم به وسط می‌آید

توی طراحی یک نرم‌افزار با عملکرد بالا، چیزی که مهمه اینه که متوجه باشیم الگوریتم‌مون از چه پیچیدگی زمانی‌ای استفاده می‌کنه.

پیچیدگی O(1)

مفهوم: پیچیدگی زمانی ثابت (Constant)، یعنی هر ورودی که بهش بدی، یک میزان ثابت زمان می‌بره که اجرا بشه، یعنی عملکردش وابسته به سایز ورودی نیست.

مثال: دسترسی به یک المان آرایه به کمک index اون و یا اضافه یا حذف کردن یک المان از یک hash table. (جدول هش ساختار داده‌ای هست که از جنس key, value هست و به کلیدهاش به مقادیرش دسترسی پیدا می‌کنیم.)

پیچیدگی O(log n)

مفهوم: پیچیدگی زمانی لگاریتمی (Logarithmic)، یعنی اینکه زمان اجرا با سرعت کمتری نسبت به رشد ورودی افزایش پیدا می‌کنه. میشه اینطور در نظر گرفت که با ضریب حدودا نیم به ۱ زمان نسبت به ورودی اضافه میشه.

مثال: جستجوی دودویی (binary search) روی یک آرایه مرتب و یا عملیات روی یک درخت جستجوی دودویی بالانس شده.

پیچیدگی O(n)

مفهوم: پیچیدگی زمانی خطی (Linear)، یعنی اینکه با نسبت ۱ به ۱ (مستقیم) براساس ورودی الگوریتم، تایم اجراش بیشتر میشه.

مثال: پیدا کردن مینیموم و ماکسیموم در یک آرایه غیر مرتب.

پیچیدگی O(n logn)

مفهوم: پیچیدگی خطی لگاریتمی (Linearithmic)، این ترکیبی از پیچیدگی زمانی خطی و لگاریتمی هست. یعنی مثلا چیزی در حدود ۱.۵ به ۱ زمان نسبت به ورودی رشد می‌کنه.

مثال: روش‌های مرتب‌کردن عملکرد بالا مثل merge sort, quick sort, heap sort. در واقع میشه گفت یک لوپ روی ورودی دارن که درونش یک لوپ روی نصف ورودی داره.

پیچیدگی O(n^2)

مفهوم: پیچیدگی زمانی توان ۲ (Quadratic)، زمان اجرا به صورت تصاعدی با سایز ورودی اضافه میشه.

مثال: الگوریتم‌های مرتب کردن ساده مثل bubble sort, insertion sort, selection sort. در واقع الگوریتم‌هایی که دو بار لوپ روی ورودی میزنن.

پیچیدگی O(n^3)

مفهوم: پیچیدگی زمانی توان ۳ (Cubic)، زمان اجرا خیلی بیشتر با هر افزایش ورودی بسیار بیشتر اضافه میشه.

مثال: الگوریتم ضرب دو ماتریکس با یک الگوریتم ابتدایی، در واقع میشه گفت کدی که ۳ لوپ تو در تو روی وردی‌ها داره.

پیچیدگی O(2^n)

مفهوم: پیچیدگی زمانی نمایی (Exponential)، با اضافه شدن هر ورودی جدید، زمان اجرا ۲ برابر میشه، این وحشتناکه، برای درکش مثال بزنم، مثلا با ۵ ورودی ۱ ثانیه طول می‌کشه، با ۶ تا ۲ ثانیه، با ۷ تا ۴ ثانیه، می‌تونین حساب کنین با ۲۰ تا چند ثانیه؟ به نظر یه چیزی حدود ۱۲ روز میشه :)

مثال: الگوریتم‌هایی که به صورت بازگشتی (recursive) مسائل رو با تقسیم کردن به چندین زیر مساله حل می‌کنن.

پیچیدگی O(n!)

مفهوم: پیچیدگی زمانی فاکتوریل (Factorial)، با افزایش ورودی سر به فلک می‌کشه :))

مثال: الگوریتم‌هایی که همه حالت‌های ممکن رو چک می‌کنن تا به جواب درست برسن، الگوریتم‌های جای‌گشت (Permutation Algorithms).

پیچیدگی O(sqrt(n))

مفهوم: پیچیدگی زمانی جزر (Square root)، زمان اجرا متناسب با جزر ریشه ورودی اضافه میشه.

مثال: در واقع الگوریتم‌هایی که توش یک لوپ با گام‌های جزر n داریم، مثل الگوریتم پیدا کردن اعداد اول.

ترتیب عملکرد

همه پیچیدگی زمانی‌هایی که آوردم به ترتیب عملکرد از کارا ترین آورده شده، فقط پیچیدگی جزری رو آخر آوردم چون متداول نیست ولی در عمل بین لگاریتمی و خطی قرار می‌گیره.

با سپاس از ByteByteGo برای این اینفوگراف خوشگلش :)