تالار گفتمان مانشت
سوال ساختمان داده(کتاب الگوریتم مقسمی و ساختمان داده طورانی) - نسخه‌ی قابل چاپ
سوال ساختمان داده(کتاب الگوریتم مقسمی و ساختمان داده طورانی) - Majiid - 02 آبان ۱۳۹۵ ۰۹:۲۱ ب.ظ

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

RE: سوال ساختمان داده(کتاب الگوریتم مقسمی و ساختمان داده طورانی) - Pure Liveliness - 02 آبان ۱۳۹۵ ۱۰:۴۳ ب.ظ

سلام.
اینکه اومده دو تا مرتبه‌ی اجرایی رو به هم تقسیم و اینا کرده، قاطی پاتی شده!
ما همیشه مرتبه‌ی الگوریتم رو همون زمان اجرا می‌گرفتیم، چون فرض می‌کردیم سرعت پردازنده ثابت هست. مثلاً [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]

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

در سوال ۱۴ گفته که تعداد داده‌ها رو از ۱۰ به ۱۰۰ می‌رسونیم. مرتبه‌ی الگوریتم [tex]n^2[/tex] هست. بالا مثال زده بودم که اگه تعداد داده‌ها دو برابر بشه، چه اتفاقی رو [tex]T(n)[/tex] می‌افته ولی الان باز میگم. وقتی مرتبه [tex]n^2[/tex] هست، یعنی تعداد سیکل‌هایی که برای n داده نیاز هست، ضریبی از [tex]n^2[/tex] هست. پس وقتی تعداد ورودی‌ها رو ۱۰ برابر می‌کنیم، تعداد سیکل‌های لازم ۱۰۰ برابر می‌شه. یعنی اگه تعداد سیکل‌ها برای ۱۰ داده برابر با ۵۰ بوده، الان برای ۱۰۰ داده میشه ۵۰۰۰/ از آنجایی که سرعت کامپیوتر ثابت هست، پس خب ۱۰۰ برابر طول میکشه که این داده‌ها پردازش بشن.
اگه این وسط گفته بود که سرعت کامپیوتر هم ۴ برابر میشه، این سری ۲۵ برابر طول میکشید. کلاً یه نسبت تناسب ساده هست و نیازی به فرموله کردن و ... نیست

RE: سوال ساختمان داده(کتاب الگوریتم مقسمی و ساختمان داده طورانی) - Majiid - 03 آبان ۱۳۹۵ ۰۹:۵۴ ق.ظ

(۰۲ آبان ۱۳۹۵ ۱۰:۴۳ ب.ظ)Pure Liveliness نوشته شده توسط:  سلام.
اینکه اومده دو تا مرتبه‌ی اجرایی رو به هم تقسیم و اینا کرده، قاطی پاتی شده!
ما همیشه مرتبه‌ی الگوریتم رو همون زمان اجرا می‌گرفتیم، چون فرض می‌کردیم سرعت پردازنده ثابت هست. مثلاً [tex]T(n)=n\cdot\log(n)[/tex] این معنی رو میده...
خیلی خیلی ممنونم.