زمان اجرای هر الگوریتم قسمت 1

[hercool]

برای اینکه سوالات در یک تاپیک نباشه هم راحت دسترس پذیر تر بشه و از شلوغی در تاپیک جدا زمان اجرای الگوریتم رو گذاشتم
ممنون میشم دوستان راهنمایی کنن
سلام خدمت دوستان چند تا سوال رو حل کردم از دوستان می خوام راهنمایی کنن ببینند من درست حل کردم

x=0
for(i=0 ; i<n; i++)
for(j=i ; j<n; j++)
x++;

جواب میشه 2n^2+2n+1

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

جواب 2n^2+2n+2

p=0;
for(i=1; i<n;i++)
for(j=i+1; j<=m ; j++)
p++;

جوابn^2+nm+n-ni+1

m=0;
for(i=0; i<n; i++)
for(j=i+1; j<n ;j++)
for(k=j+1; k<n; k++)
m++;

جواب n^3+2n^2+n+ni+nj+2

l=0;
for(i=0; j<n; i++)
for(j=0; j<m; j++)
for(k=0; k<p;k++)
l++;

جوابn^3+nm+2n+mp+m+1


اینا رو خودم حل کردم
ممنون میشم دوستان چک کنن ایرادات رو بگند ببینم کجا مشکل دارم

[hercool]

کسی نظری نداره

[Arcsinos]

دوست عزیز حالا نمیدونم چطوری اینو حل کردی ولی من در آووردم

l=0;

for(i=0; j<n; i++)

  for(j=0; j<m; j++)

    for(k=0; k<p;k++)

l++;

n*m*p*d
که d یه عدد ثابته
روشش هم اینه

[mohsensaghafi]

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

(n^2+n)/2

و واسه دومی

(n^2-n)/2

نمونه برنامه ای هم که باید بنویسی و چک کنی واسه مثال دوم به شکل زیر می شه.

#include <iostream.h>

#include <stdio.h>





void main(){

	int n=5;

	int x=0;

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

		for(int j=0; j<i; j++)

			x++;

	cout<<x<<endl;

	getchar();

}

موفق باشی

[hercool]

برای سوال اول می گم چجوری حل کردم تا شاید ایرادم پیدا بشه

x=0
for(i=0 ; i<n; i++)
for(j=i ; j<n; j++)
x++;

برای سطر اول عدد 1 میشه
برای سطر دوم حد بالا رو منهای حد پایین می کنم بعلاوه 1 می کنم
میشه n-0+1 بنابراین میشه n+1
برای سطر سوم مقدار بالا را باید در n ضرب کنم میشه
n(n+1)=n^2+n این میشه برای سطر سوم
حالا سطر چهارم میشه n*n که میشه n^2
حالا بالاترین درجه این جمله n^2 است اما کل جمله اونی هست که نوشتم و شما گفتید ایراد داره ممنون میشم بگید ایراد کجاست

اگر هم بگید در قسمت دومی که حل کردید چرا منها شده
منتظر کمک دوستان هستم تقریبا چند ساعت دیگه باید برم امتحان بدم
فکر کردم درست حل کرده باشم
منتظر راهنماییهاتون و کمکتون هستم
با تشکر

[Arcsinos]

سوال دوم :

(n^2+n)/2

[hercool]

یک سوال محسن خان جوابش منها داره و برای شما + میشه بیشتر راهنمایی کنید
ایا میشه گفت بالاترین تعداد حلقه را مرتبه زمانیش را میگیریم بر تعداد حلقه ها تقسیم می کنیم؟
ممنون میشم ایراد محاسبه من رو بگید

[Arcsinos]

سوال اول هم :

(n^2-n)/2

[Arcsinos]

مشکل شما همینجاست
عدد j=i ولی شما اونو صفر در نظر میگیری یعنی j=0 و ادامه میدید . این روشی که شما پیش گرفتید برای سوالهای ساده است و خوب هم جواب میده ولی وقتی توابع بازگشتی و استفاده از یه متغیر جدید تو حلقه ها که اینجا (i) هست به میون میاد دیگه باید از سیگما گرفتن استفاده کرده.
موفق باشی

[mohsensaghafi]

سوال دوم :

(n^2+n)/2

سلام دوستان.
با توجه به فرمولهایی که بدست آوردید، با یک تکه کد هم در جالت اجرا آنها را چک کنید.
مشکلی که دوست عزیزمون Arcsinos در جوابشون وجود داره در زمان تبدیل حلقه ها به سیگما هست. دوستان توجه داشته باشید که در حلقه های موجود در حد بالا علامت کوچکتر وجود دارد، نه کوچکتر مساوی. برای همین حد بالا مثلا در مثال اول برابر n-1 است نه n. برای همین در جواب ها تغییر علامت وجود دارد. لطفا به این نکته توجه کنید. همچنین در استفاده و ساده سازی متغیر d که در بعضی جاها اشتباها حذف شده است. برای سادگی کار می توان پیچیدگی زمانی دستور درون حلقه ها که یک انتساب ساده است را برابر 1 درنظر گرفت. لطفا به این موارد توجه کنید.
موفق و پیروز

[mohsensaghafi]

مشکل شما همینجاست
عدد j=i ولی شما اونو صفر در نظر میگیری یعنی j=0 و ادامه میدید . این روشی که شما پیش گرفتید برای سوالهای ساده است و خوب هم جواب میده ولی وقتی توابع بازگشتی و استفاده از یه متغیر جدید تو حلقه ها که اینجا (i) هست به میون میاد دیگه باید از سیگما گرفتن استفاده کرده.
موفق باشی

سلام دوست عزیز.
پاسخ کاملا کامل و درست است. از دوستمان Arcsinos تشکر می کنم. در عین حال می توانید و بست دادن حلقه و بازنویسی متوالی از حلقه ها هم به جواب برسید. فقط به حد بالا و پایین دقت فراوان کنید.

[mohsensaghafi]

سوال اول هم :

(n^2-n)/2

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

[mohsensaghafi]

یک سوال محسن خان جوابش منها داره و برای شما + میشه بیشتر راهنمایی کنید
ایا میشه گفت بالاترین تعداد حلقه را مرتبه زمانیش را میگیریم بر تعداد حلقه ها تقسیم می کنیم؟
ممنون میشم ایراد محاسبه من رو بگید

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