logarithmic یعنی چه؟
تلفظ: لاگِریذمیک · نوع: صفت
معنی logarithmic: لگاریتمی
logarithm (لگاریتم) برعکس توان است: log₂ 8 میپرسد 2 را به چه توانی برسانیم تا 8 شود؟ جواب 3 است. logarithmic time یعنی O(log n): هر قدم ورودی را نصف میکند، مثل binary search. برای همین در یک میلیون عضو فقط حدود بیست قدم لازم است.
logarithmic در جمله
Binary search runs in logarithmic time because it halves the range each step.
جستوجوی دودویی زمان لگاریتمی دارد، چون در هر قدم بازه را نصف میکند.
logarithmic در کد
import math
print(math.log2(1_000_000)) # 19.931568569324174یعنی جستوجوی دودویی در یک میلیون عضو حدود 20 قدم طول میکشد.
نکته
log n را «log n» بخوان. در کامپیوتر وقتی مبنا را نمیگویند، معمولاً منظور log در مبنای 2 است. log به معنی «گزارش» کلمهی دیگری است.
کلمههای مرتبط
- binary search: جستوجوی دودویی؛ هر بار نصف کردن
- linear: خطی
- exponential: نمایی
درس این کلمه
logarithmic یکی از هشت کلمهی درس «سرعت الگوریتم» در فاز 16: ریاضی و منطق به انگلیسی از دورهی انگلیسی برای برنامهنویسها است. بقیهی کلمههای این درس:
- order of magnitude: مرتبهی بزرگی؛ حدود ده برابر
- big O notation: نماد O بزرگ؛ روش نوشتن پیچیدگی الگوریتم
- linear: خطی
- exponential: نمایی
- constant time: زمان ثابت؛ O(1)
- worst case: بدترین حالت
- approximately: تقریباً