مفهوم پیچیدگی محاسباتی

[negar.v]

سلام دوستان،کسی می تونه مفهوم پیچیدگی محاسباتی رو با یک مثال ساده واسه من توضیح بده؟

مثلا وقتی میگن به دست آوردن جمع اعداد یک تا n با استفاده از یک حلقه ساده دارای پیچیدگی محاسباتی (O(n است و حل با استفاده از n(n+1))/2دارای

(O(1
constatnt time یعنی چی؟چطور این پیچیدگی ها به دست میان؟

[aqm176]

سلام.
در این بابت کتاب ساختمان داده قلزم رو از پی سی دانلود، دانلود کنید و فصل چیپیدگی الگوریتم رو مطالعه کنید که بس طولانی و درک بالا میخواهد.
لذا باید درک از تعداد دستورات در واحد زمانی cpu داشته باشید.

بدرود.

[علیرضا.ا]

در برنامه نویسی دو نوع پیچیدگی داریم: زمانی و فضایی
توی پیچیدگی فضایی میاییم فضای مصرفی برنامه رو تحلیل میکنیم توی پیچیدگی زمانی بدترین زمان ممکن با افزایش ورودی
مثلا این حلقه:

int s=0;
for(int i=0;i<n;i++)
s+=i;


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

توی همه ی جزوت یا کتاب هاس ساختمان داده این بحثو کامل توضیح دادن..