چرا پیچیدگی زمانی الگوریتم افراز کردن میشه n-1؟

[sajad_3dmax]

با سلام خدمت دوستان. در جستجوی quick sort زیربرنامه ای برای پیدا کردن pivot وجود دارد به این ترتیب که در دو حلقه repeat...until جستجویی را انجام میدهد. چرا پیچیدگی زمانی این زیر الگوریتم در جستجوی quick sort میشه n-1؟مگه دو تا حلقه نداریم که در اونها همه عناصر بجز خود pivot باpivotمقایسه میشند.پس باید پیچیدگی رو بگیریم 2n-1.من محاسبه کردم اینطور نتیجه محاسبه الگوریتم بازگشتی دقیقتر هم میشه اما در اکثر کتابهای معتبر پیچیدگیش رو گرفتن n-1.
پیچیدگیn, 2n,100000n از یک order هستند اما وقتی گفته شده پیچیدگی الگوریتمی n-1 هست میزان دقیق اون گفته شده. حداقل در بدترین حالت الگوریتم(آرایه از قبل مرتب باشد) میتوان اثبات کرد که n+1 پیمایش صورت میپذیرد.1 پیمایش از سمت چپ و n پیمایش از سمت راست. لطفا راهنماییم کنین.با تشکر

[Mahdi1001]

سلام
این چیزی كه شما مى گين من تا حالا جاى نديدم.
تمام algorithm ها n-۱ بر اجرا ميشوند .
دقت بكنين ۲ حلقِ بيانگر 2n نيس ممكنه هركدام تا n/۲ اجرا شوند.
اما اگر اينطور نبود حتما algorithm را بگذاريد

Eshaghi@ce.sharif.edu
موفق باشید

[sajad_3dmax]

الگوریتم افراز کردن در مرتب سازی quick sort:
procedure qSort (var x:arraylist;left,right:integer)
var
i,j,pivot :integer;
begin
if left < right
brgin
i:=left; j:=right+1; pivot:=x[left];
repeat
repeat
i:=i+1;
until x[i]>=pivot;
repeat
j:=j-1;
until x[j]<=pivot
if i<j then swap (x[i],x[j]);
until i>=j;
swap (x[left],x[j]);
qSort (x,left,j-1); qSort (x,j+1,right);
end
end;

[Mahdi1001]

salam
bebinin shart haye halghe :



until x[i]>=pivot;
until x[j]<=pivot
until i>=j;


inha mibashand.
ke dar majmo n bar ejra mishan dg vazehe age motavaje nemishin rahatarin kar
trace barnamas .
ye araye mesal bezanin ba yetedad onsor mibinin ke hamon n martabe ejramishe.
asan hich ja 2n nis to hich algorithmi
movafagh bashid

[sajad_3dmax]

با سلام دوست عزیز. فکر میکنم که ان شاالله مشکلم با راهنمایی شما حل شده باشه. اشتباه من این بود که پیچیدگی زمانی رو تازمانی که pivot پیدا بشه(I,j برابر هم باشن و یا از هم عبور کنند ) و جای j , pivot عوض شه حساب میکردم. ولی ظاهرا باید هر زمان I,j توقف میکنند پیچیدگی رو حساب کرد.درست میگم؟ با یک مثال توضیح میدم.مثلا آرایه ای با عناصر زیر داریم:

[1] [2] [3] [4] [5] [6] [7] [8]
10 5 3 14 7 15 4 9


عنصر اول(10) رو pivot میگیریم. در اولین پیمایش I,j ، i با 3 پیمایش در خانه[4]=14 ومتغیر j با 1 پیمایش در خانه[8]=9 توقف میکنند. پس پیچیدگی زمانی در این مرحله میشود n-4=4 .و آرایه بصورت زیر در می آید:
[1] [2] [3] [4] [5] [6] [7] [8]
10 5 3 9 7 15 4 14


و در مرحله دوم i با 2 پیمایش در خانه[6]=15 ومتغیر j با 1 پیمایش در خانه[7]=4توقف میکنند. پس پیچیدگی زمانی در این مرحله میشود n-5=3 .و آرایه بصورت زیر در می آید:
[1] [2] [3] [4] [5] [6] [7] [8]
10 5 3 9 7 4 15 14


و در مرحله سوم i با 1 پیمایش در خانه[7]=15 ومتغیر j با 1 پیمایش در خانه [6]=4توقف میکنند. پس پیچیدگی زمانی در این مرحله میشود n-6=2.والبته چون I,j از هم عبور کرده اند جای عناصر با اندیس j,pivot را با هم عوض میکنیم که آرایه بصورت زیر در می آید:
[1] [2] [3] [4] [5] [6] [7] [8]
4 5 3 9 7 10 15 14

و 10 در جای خود قرار گرفته است. بده پیش از این پیچیدگی را تا این مرحله حساب میکردم.یعنی t(n)=2+3+4=9 که از n-1 بیشتر میشد.
پس اگر چنین باشد در بدترین حالت که آرایه از قبل مرتب باشد t(n)=n+1 میشود نه i) . n-1 با یک پیمایش و j با n پیمایش متوقف میشود)
اما ادامه سوالم از حضور محترم شما این است که جنابعالی فرموده بودبن که این برنامه 3تا شرط دارد.آیا میتوان تنها یکی از آنها را (نه تنها در این کد بلکه در هر کد مشابهی)ملاک پیچیدگی قرار داد؟یعنی فقط حرکت I یا j یا تعداد دفعاتی که این دو می ایستند و موقعیتشان را بررسی میکنیم؟که اگر چنین باشد مشکل بالا هم حل خواهد شد

[Mahdi1001]

سلام
بله دقیقا همینطوره.
اما در بدترین حالت فقط یکم باید دقت کنین اگه i به j برسه دیگه j افزایش پیدا نمی کند.
در کل n-1 با n با n+1 در مرتبه زمانی کل تاثیری ندارد اما اگه بخواین به طور دقیق می توانید با همین روش که مثال عددی بزنین بدست بیارین.

[sajad_3dmax]

جناب mahdi1001جسارتا دو تا سوال داشتم.در الگوریتم ضرب استراسن پیچیدگی زمانی برابراست با 7t(n/2)+(n/2)^2
این توان دو برای جمع ها بعلت این است که جمع ماتریس ها از مرتبه 2 است ؟ یا دلیل دیگری دارد؟
سوال دوم:چرا در تحلیل بعضی از الگوریتمها بجای n قرار میدهند cn.میشود مثالی بزنید؟ با تشکر

[Mahdi1001]

ببخشید من واقعا سرم شلوغ و کلا ماهی یک بار میام یه سر می زنم. از این باب گفتم که اگه سوال پرسیدین جواب ندادم ناراحت نشین.
ج1) بله همینطور است
ج2) چون مقدار n, 2n , 100n, 10000n به لحاظ مرتبه زمانی O = 'ا و ، امگا و تتا ' تاثیری ندارند . و c یک عدد ثابت است .
اگه تهران هستین می تونین سر کلاس های طراحی الگوریتم بیاین مانعی نیست.