تالار گفتمان مانشت

سلام.
وقت بخیر.
میشه لطف کنید این مثال ها رو توضیح بدین؟
[attachment=20710]
ممنونم.

سلام.
اینکه اومده دو تا مرتبه‌ی اجرایی رو به هم تقسیم و اینا کرده، قاطی پاتی شده!
ما همیشه مرتبه‌ی الگوریتم رو همون زمان اجرا می‌گرفتیم، چون فرض می‌کردیم سرعت پردازنده ثابت هست. مثلاً [tex]T(n)=n\cdot\log(n)[/tex] این معنی رو میده که مدت زمان اجرای برنامه با n ورودی، ضریبی از [tex]n\cdot\log(n)[/tex] هست. حالا اگه تعداد ورودی‌ها رو دو برابر کنند و از شما زمان اجرا رو بخواهند، میشه [tex]2n\cdot\log(2n)[/tex] که نسبت به قبلی میشه [tex]\frac{2n\cdot\log(2n)}{n\cdot\log(n)\: }=2\log_n( 2n)[/tex]
حالا تنهای نکته‌ای که اضافه شده این هست که سرعت کامپیوتر هم ممکنه تغییر کنه. نسبت سرعت کامپیوتر با زمان اجرای الگوریتم، خطی هست و ربطی به مرتبه‌ی الگوریتم نداره. مثلاً اگر قبلاً یک الگوریتم (با هر مرتبه‌ای) مدت [tex]T[/tex] ثانیه طول میکشید که روی n داده اجرا بشه، اگر سرعت [tex]V[/tex] برابر بشه (و تعداد داده‌ها ثابت بمونه)، این بار الگوریتم [tex]\frac{T}{V}[/tex] طول می‌کشه. مرتبه‌ی الگوریتم خودش رو در تعداد سیکل‌های پردازنده نشون میده. یک الگوریتم با مرتبه‌ی [tex]T(n)=n\cdot\log(n)[/tex] روی تعداد مثلاً ۶۴ داده، ۳۸۴ سیکل اجرا میشه. شما اگه سرعت کامپیوتر رو زیاد کنی، باز همین ۳۸۴ سیکل باید اجرا بشه، منتهی این بار هر کدوم از این این سیکل‌ها، به جای ۱ نانوثانیه (وقتی فرکانس پردازنده ۱ گیگاهرتز بود) الان نیم نانوثانیه طول میکشه (فرکانس شده ۲ گیگ). پس نسبت خطی هست و میشه فرمولی که در خط اول نوشتم رو اینطوری نوشت:
[tex]T(n)\times V=O(n)[/tex]

سوال 13 گفته که همان الگوریتم روی کامپیوتری که سرعتش 100 برابر بیشتر هست چقدر طول میکشه. منظورش از "همان الگوریتم" در واقع همان تعداد داده‌ها و در واقع تعداد سیکل‌ها هست. یعنی قرار هست همان مقدار قبلی از سیکل‌ها رو، 100 برابر سریع‌تر پردازش کنیم، که خب بدیهی هست که 100 برابر زودتر تموم میکنیم و زمان از 1 ثانیه‌ی قبلی، میرسه به یک صدم ثانیه.

در سوال 14 گفته که تعداد داده‌ها رو از 10 به 100 می‌رسونیم. مرتبه‌ی الگوریتم [tex]n^2[/tex] هست. بالا مثال زده بودم که اگه تعداد داده‌ها دو برابر بشه، چه اتفاقی رو [tex]T(n)[/tex] می‌افته ولی الان باز میگم. وقتی مرتبه [tex]n^2[/tex] هست، یعنی تعداد سیکل‌هایی که برای n داده نیاز هست، ضریبی از [tex]n^2[/tex] هست. پس وقتی تعداد ورودی‌ها رو 10 برابر می‌کنیم، تعداد سیکل‌های لازم 100 برابر می‌شه. یعنی اگه تعداد سیکل‌ها برای 10 داده برابر با 50 بوده، الان برای 100 داده میشه 5000. از آنجایی که سرعت کامپیوتر ثابت هست، پس خب 100 برابر طول میکشه که این داده‌ها پردازش بشن.
اگه این وسط گفته بود که سرعت کامپیوتر هم 4 برابر میشه، این سری 25 برابر طول میکشید. کلاً یه نسبت تناسب ساده هست و نیازی به فرموله کردن و ... نیست

(02 آبان 1395 10:43 ب.ظ)Pure Liveliness نوشته شده توسط: [ -> ]سلام.
اینکه اومده دو تا مرتبه‌ی اجرایی رو به هم تقسیم و اینا کرده، قاطی پاتی شده!
ما همیشه مرتبه‌ی الگوریتم رو همون زمان اجرا می‌گرفتیم، چون فرض می‌کردیم سرعت پردازنده ثابت هست. مثلاً [tex]T(n)=n\cdot\log(n)[/tex] این معنی رو میده...

خیلی خیلی ممنونم.