PDA

View Full Version : سوال: پیچیدگی زمانی یک تابع چگونه log می شود؟



amin.m1993
جمعه 26 آبان 1391, 10:04 صبح
سلام.
میخواستم بدونم چطوری میشه که الگوریتمی مثل الگوریتم زیر که i یا ضرب در یک عدد میشه یا تقسیم بر همون عدد , log میشه؟ خیلی گشتم ولی همه جا فقط نوشتن که میشه log. لطفا توضیح کامل بدین.

i=n;
while (i>1) {
i=i/2;}
ممنون.

مسعود اقدسی فام
جمعه 26 آبان 1391, 10:31 صبح
فرض کنید i = 16 باشه. بعد می‌شه 8 و 4 و 2 که تعدادشون همون log 16 هستش. اثبات همچین رابطه‌ای در بخش روابط بازگشی کتاب‌های برنامه‌نویسی و الگوریتم و ساختمان گسسته موجوده.