بتل کد Battle Codeدارد باز می‌شود…

سرعت الگوریتم

در هر مصاحبه‌ی برنامه‌نویسی می‌پرسند «What is the time complexity?». این هشت کلمه زبان حرف زدن درباره‌ی سرعت الگوریتم‌اند و بدون آن‌ها توضیح‌های big O را نمی‌فهمی.

big O را بلند بخوان

O(n) را «O of n» یا «big O of n» بخوان، O(1) را «O of one» و O(log n) را «O of log n». O(n²) می‌شود «O of n squared» و O(n log n) «O of n log n». در جمله معمولاً با in یا takes می‌آید: «This runs in O of n time» یا «It takes linear time». صفت‌ها هم جای خودشان را دارند: linear، quadratic (درجه‌ی دو)، logarithmic و exponential.

هشت کلمه‌ی این درس

order of magnitude (اوردِر آو مَگنیتود): مرتبه‌ی بزرگی؛ حدود ده برابر

magnitude یعنی «بزرگی، اندازه». order of magnitude یعنی یک پله‌ی ده‌تایی: 1000 سه order of magnitude از 1 بزرگ‌تر است. وقتی می‌گویند «an order of magnitude faster» یعنی تقریباً ده برابر سریع‌تر. برنامه‌نویس‌ها با آن تخمین سریع می‌زنند: 10^5 عمل در یک چشم به هم زدن تمام می‌شود، 10^12 عمل هرگز.

The new query is an order of magnitude faster than the old one.

کوئری تازه حدود ده برابر از قبلی سریع‌تر است.

big O notation (بیگ اُو نُوتِیشِن): نماد O بزرگ؛ روش نوشتن پیچیدگی الگوریتم

notation یعنی «روش نوشتن با نماد». big O notation می‌گوید وقتی ورودی بزرگ می‌شود، زمان یا حافظه‌ی یک الگوریتم با چه سرعتی زیاد می‌شود. O(n) را «O of n» یا «big O of n» می‌خوانند و O(n²) را «O of n squared». ضریب‌ها و جمله‌های کوچک را کنار می‌گذارند، چون فقط شکل رشد مهم است.

In big O notation, binary search is O(log n).

با نماد O بزرگ، جست‌وجوی دودویی O(log n) است.

linear (لینیِر): خطی

line یعنی «خط» و linear یعنی «خطی». در الگوریتم‌ها linear time یعنی O(n): اگر ورودی دو برابر شود، زمان هم حدود دو برابر می‌شود، مثل یک بار رد شدن از روی فهرست. linear search یعنی جست‌وجوی یکی‌یکی از اول تا آخر. در ریاضی linear equation معادله‌ای است که نمودارش خط راست است.

A linear search checks every element until it finds the target.

جست‌وجوی خطی همه‌ی عضوها را یکی‌یکی بررسی می‌کند تا هدف را پیدا کند.

exponential (اِکسپِنِنشِل): نمایی

exponential از exponent (نما) می‌آید. رشد exponential یعنی با هر قدم، مقدار چند برابر می‌شود؛ مثل O(2^n) که با یکی بزرگ‌تر شدن ورودی، زمان دو برابر می‌شود. الگوریتمی که همه‌ی زیرمجموعه‌ها را امتحان می‌کند exponential است و حتی برای n = 40 خیلی کند است.

Trying every subset takes exponential time, so it only works for small n.

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

logarithmic (لاگِریذمیک): لگاریتمی

logarithm (لگاریتم) برعکس توان است: log₂ 8 می‌پرسد 2 را به چه توانی برسانیم تا 8 شود؟ جواب 3 است. logarithmic time یعنی O(log n): هر قدم ورودی را نصف می‌کند، مثل binary search. برای همین در یک میلیون عضو فقط حدود بیست قدم لازم است.

Binary search runs in logarithmic time because it halves the range each step.

جست‌وجوی دودویی زمان لگاریتمی دارد، چون در هر قدم بازه را نصف می‌کند.

constant time (کانستِنت تایم): زمان ثابت؛ O(1)

constant یعنی «ثابت». constant time یعنی کاری که زمانش به اندازه‌ی ورودی بستگی ندارد و با O(1) نوشته می‌شود: خواندن list[5] یا پیدا کردن یک کلید در dict، چه ده عضو داشته باشد چه ده میلیون. amortized constant time یعنی «به طور میانگین ثابت»، مثل append در پایتون.

Looking up a key in a dictionary takes constant time on average.

پیدا کردن یک کلید در دیکشنری به طور میانگین زمان ثابت می‌برد.

worst case (وِرست کِیس): بدترین حالت

worst یعنی «بدترین» و case یعنی «حالت». worst case یعنی ورودی‌ای که الگوریتم را از همه کندتر می‌کند؛ big O معمولاً همین را می‌گوید. مثلاً quicksort معمولاً O(n log n) است ولی در worst case به O(n²) می‌رسد. کنارش best case و average case را هم می‌شنوی.

In the worst case, the loop runs n times before it finds the item.

در بدترین حالت، حلقه n بار اجرا می‌شود تا عضو را پیدا کند.

approximately (اِپراکسِمِتلی): تقریباً

approximate یعنی «تقریبی» و approximately یعنی «تقریباً». در مستندات و مسئله‌ها برای عددهایی می‌آید که دقیق نیستند: approximately 10^8 operations per second. علامتش ≈ است و «is approximately equal to» خوانده می‌شود. در گفتار به جایش about یا roughly هم می‌گویند.

Python runs approximately ten million simple operations per second.

پایتون تقریباً ده میلیون عمل ساده در ثانیه انجام می‌دهد.

big O در یک دقیقه

Big O in one minute
Big O notation describes how the running time grows when the input grows. It ignores small details and keeps only the order of magnitude.
O(1) is constant time: reading a dictionary key takes the same time for any size. O(n) is linear: you look at each item once. O(log n) is logarithmic: binary search halves the range every step. O(2^n) is exponential: trying every subset doubles the work for each new item.
We usually talk about the worst case. A rule of thumb: a fast language does approximately 10^8 simple operations per second, and Python is often 10 to 50 times slower.

big O در یک دقیقه
نماد big O می‌گوید وقتی ورودی بزرگ می‌شود، زمان اجرا چطور زیاد می‌شود. جزئیات کوچک را کنار می‌گذارد و فقط مرتبه‌ی بزرگی را نگه می‌دارد.
O(1) زمان ثابت است: خواندن یک کلید از دیکشنری برای هر اندازه‌ای همان‌قدر طول می‌کشد. O(n) خطی است: هر عضو را یک بار نگاه می‌کنی. O(log n) لگاریتمی است: جست‌وجوی دودویی در هر قدم بازه را نصف می‌کند. O(2^n) نمایی است: امتحان کردن همه‌ی زیرمجموعه‌ها با هر عضو تازه کار را دو برابر می‌کند.
معمولاً درباره‌ی بدترین حالت حرف می‌زنیم. یک قاعده‌ی سرانگشتی: یک زبان سریع تقریباً ۱۰ به توان ۸ عمل ساده در ثانیه انجام می‌دهد و پایتون معمولاً ۱۰ تا ۵۰ برابر کندتر است.