big O notation یعنی چه؟
تلفظ: بیگ اُو نُوتِیشِن · نوع: اسم
معنی big O notation: نماد O بزرگ؛ روش نوشتن پیچیدگی الگوریتم
notation یعنی «روش نوشتن با نماد». big O notation میگوید وقتی ورودی بزرگ میشود، زمان یا حافظهی یک الگوریتم با چه سرعتی زیاد میشود. O(n) را «O of n» یا «big O of n» میخوانند و O(n²) را «O of n squared». ضریبها و جملههای کوچک را کنار میگذارند، چون فقط شکل رشد مهم است.
big O notation در جمله
In big O notation, binary search is O(log n).
با نماد O بزرگ، جستوجوی دودویی O(log n) است.
big O notation در کد
total = 0
for i in range(n):
for j in range(n):
total += i * j # O(n^2)دو حلقهی تودرتو تا n یعنی n ضرب در n قدم؛ بخوان «O of n squared».
نکته
O را حرف «اُو» بخوان، نه «zero». O(1) را «O of one» و O(n log n) را «O of n log n» میخوانند.
کلمههای مرتبط
- complexity: پیچیدگی؛ اینکه با بزرگ شدن داده کار چقدر بیشتر میشود
- constant time: زمان ثابت؛ O(1)
- worst case: بدترین حالت
درس این کلمه
big O notation یکی از هشت کلمهی درس «سرعت الگوریتم» در فاز 16: ریاضی و منطق به انگلیسی از دورهی انگلیسی برای برنامهنویسها است. بقیهی کلمههای این درس:
- order of magnitude: مرتبهی بزرگی؛ حدود ده برابر
- linear: خطی
- exponential: نمایی
- logarithmic: لگاریتمی
- constant time: زمان ثابت؛ O(1)
- worst case: بدترین حالت
- approximately: تقریباً