آنالیز زمانی یک الگوریتم مثل quicksort

[sarax]

بچه ها چجوری میشه آنالیز زمانی یک الگوریتم مثل مثلا quicksort رو بدست آورد؟از کجا باید شروع کرد و به چه چیزهایی توجه کرد؟

 

[negin17h]

بچه ها چجوری میشه آنالیز زمانی یک الگوریتم مثل مثلا quicksort رو بدست آورد؟از کجا باید شروع کرد و به چه چیزهایی توجه کرد؟

سلام
سارا جان ببین اصلاً کار سختی نیست.
شما الگوریتم یا شبه کد یا کد را بذار جلوت که دو مورد دوم راحت تره.
دقیقاً برای حلقه هاش از سیگماهای تو در تو استفاده کن و حد سیگما رو هم از خود حلقه بذار. یه فرمول ریاضی در میاد که با استفاده از روابط سیگما که در ریاضی 1 هم دارید به سادگی حل میشه.
سعی میکنم یه تکه از جزوه ام رو اسکن کنم بذارم واستون

 

[afra.mehrparvar]

برای پیدا کردن زمان یک الگوریتم نگاه کن ببین جندتا حلقه تکرار از یک تا n هست .. بعد تویی ترین حلقه بیش ترین زمان رو داره و بیشترین زمان زمان اجرای الگوریتم هستش

فقط تعداد تکرار حلقه های 1..n یا 1..n-1 قابل توچه هستش مثلا اینجا در کئ زیر زمان اجرا n^2 هستش (ان به توان 2 )

for i = 1 to n do
cin>>j
for j = 1 to n-1 do
cout<<j+2

cin j زمانش n هست چون در یک حلقه د تایی تکرار
اما cout<<j+2 چون در دو حلقه تکرار n تایی قرار دارد پس n X n = n^2 زمان دارد . این امر به تمام الگوریتم ها بست پیدا می کند

اینجا خط

 

[negin17h]

برای پیدا کردن زمان یک الگوریتم نگاه کن ببین جندتا حلقه تکرار از یک تا n هست .. بعد تویی ترین حلقه بیش ترین زمان رو داره و بیشترین زمان زمان اجرای الگوریتم هستش

فقط تعداد تکرار حلقه های 1..n یا 1..n-1 قابل توچه هستش مثلا اینجا در کئ زیر زمان اجرا n^2 هستش (ان به توان 2 )

for i = 1 to n do
cin>>j
for j = 1 to n-1 do
cout<<j+2

cin j زمانش n هست چون در یک حلقه د تایی تکرار
اما cout<<j+2 چون در دو حلقه تکرار n تایی قرار دارد پس n X n = n^2 زمان دارد . این امر به تمام الگوریتم ها بست پیدا می کند

اینجا خط

این در صورتی درسته که شمارنده حلقه های شما وابسته نباشند