مرتبه زمانی الگوریتم زیر
sum=0,i=1
while sum<n do{
sum=sum+1/i
i=i+1
}
چیست؟
میشه راه حلی که در عکس پیوست شده گذاشتم توضیح بدین؟
(۲۸ آبان ۱۳۹۱ ۰۹:۵۱ ب.ظ)hana.rahmati نوشته شده توسط: مرتبه زمانی الگوریتم زیر
sum=0,i=1
while sum<n do{
sum=sum+1/i
i=i+1
}
چیست؟
میشه راه حلی که در عکس پیوست شده گذاشتم توضیح بدین؟
سلام
به نظرم تست زیبایی هست ممنون که پرسیدی (آخه خودم هم یه چیزی یاد گرفتم) ماجرا از این قرار است که :
حاصل این سری : [tex]\frac{1}{1} \frac{1}{2} \frac{1}{3} \frac{1}{4}... \frac{1}{n}[/tex]
در ریاضیات میشود : [tex]ln(n)[/tex]
تا اینجا رو بدون دلیل قبول کن (این سری معروف به سری هارمونیک یا همسازه است که تقریبآ برابر است با الگاریتم ان در مبنا e )
فرض کن این حلقه به تعداد مثلآ m بار دور میزند و باعث میشه که حاصل sum بشود : [tex]\frac{1}{1} \frac{1}{2} \frac{1}{3} \frac{1}{4}... \frac{1}{m}[/tex] و طبق نکته ایی که گفتم حاصل این سری میشود : [tex]ln(m)[/tex]
خوب طبق شرط حلقه باید sum بلاخره برسه به n و ما میدانیم که داخل sum مقدار :[tex]ln(m)[/tex] قرار داره، بنابراین :
وقتی حلقه تمام خواهد شد که : ln(m)=n
یادآوری : [tex](\log_{a}^{b}=x) \Rightarrow a^{x}=b[/tex] در نتیجه : [tex](\log_{e}^{m}=n) \Rightarrow e^{n}=m[/tex]
و در نهایت میفهمیم که این حلقه به اندازه : [tex]e^{n}[/tex] بار دور خواهد زد که تابعی نمایی است. ([tex]e\approx 2.7[/tex]
)