سلام. لطفا پیچیدگی زمانی تکه برنامه زیر رو بگید چقدر است؟
for(int i =0 ; i < =n ; i++)
for(int j =1; j<= i^2; j++)
if (j % i == 0)
for(int k = 0; k<j; k++)
; sum++
سلام.
راه اول:
در صورتی حلقه k به تعداد j بار اجرا میشه که --> j بر i بخش پذیر باشه-->
پس در صورتی که j برابر : [tex]i\: or\: 2i\: or\: 3i\: or\: ...\: or\: ii[/tex] باشه،حلقه k به تعداد j بار اجرا میشه.
پس تعداد دفعات تکرار حلقه k برابر:
[tex]i\: \: 2i\: 3i\: \: ...\: \: ii[/tex] هستش. که برابر [tex]i\: \times\frac{i(i 1)}{2}\: =\frac{\: 1}{2}\: \times(i^3\: \: i^2)[/tex] هستش.
و با توجه با اینکه i از ۰ تا n هستش،پس جواب برابر :[tex]\frac{1}{2}\: \sum\: \: (i^3\: \: i^2)\: =\: \theta(n^4)[/tex] (سیگما از ۰ تا n)
پس جواب میشه [tex]\theta\: \: (n^4)[/tex]
راه دوم:
[tex]i=0\: \rightarrow\: -[/tex]
[tex]i=1\: \rightarrow\: \: j=1\: \rightarrow\: Tedad\: tekrar\: k\: :\: 1[/tex]
[tex]i=2\: \rightarrow\: \: j=1\: \rightarrow\: Tedad\: tekrar\: k\: :\: [/tex]
[tex]\: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: j=2\: \rightarrow\: Tedad\: tekrar\: k\: :\: 2[/tex]
[tex]\: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: j=3\: \rightarrow\: Tedad\: tekrar\: k\: :\: [/tex]
[tex]\: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: j=4\: \rightarrow\: Tedad\: tekrar\: k\: :\: 4[/tex]
[tex]i=3\: \rightarrow\: \: j=1\: \rightarrow\: Tedad\: tekrar\: k\: :\: [/tex]
[tex]\: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: j=2\: \rightarrow\: Tedad\: tekrar\: k\: :\: [/tex]
[tex]\: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: j=3\: \rightarrow\: Tedad\: tekrar\: k\: :\: 3 [/tex]
[tex]\: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: j=4\: \rightarrow\: Tedad\: tekrar\: k\: :\: [/tex]
[tex]\: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: j=5\: \rightarrow\: Tedad\: tekrar\: k\: :\: [/tex]
[tex]\: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: j=6\: \rightarrow\: Tedad\: tekrar\: k\: :\: 6 [/tex]
[tex]\: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: j=7\: \rightarrow\: Tedad\: tekrar\: k\: :\: [/tex]
[tex]\: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: j=8\: \rightarrow\: Tedad\: tekrar\: k\: :\: [/tex]
[tex]\: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: j=9\: \rightarrow\: Tedad\: tekrar\: k\: :\: 9[/tex]
.
.
.
[tex]i=1\: \rightarrow\: \: j=1\: \rightarrow\: Tedad\: tekrar\: k\: :\: 1[/tex]
[tex]i=2\: \rightarrow\: \: j=1\: \rightarrow\: Tedad\: tekrar\: k\: :\: [/tex]
[tex]\: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: j=2\: \rightarrow\: Tedad\: tekrar\: k\: :\: 2[/tex]
[tex]\: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: j=3\: \rightarrow\: Tedad\: tekrar\: k\: :\: [/tex]
[tex]\: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: j=4\: \rightarrow\: Tedad\: tekrar\: k\: :\: 4[/tex]
[tex]i=3\: \rightarrow\: \: j=1\: \rightarrow\: Tedad\: tekrar\: k\: :\: [/tex]
[tex]\: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: j=2\: \rightarrow\: Tedad\: tekrar\: k\: :\: [/tex]
[tex]\: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: j=3\: \rightarrow\: Tedad\: tekrar\: k\: :\: 3 [/tex]
[tex]\: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: j=4\: \rightarrow\: Tedad\: tekrar\: k\: :\: [/tex]
[tex]\: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: j=5\: \rightarrow\: Tedad\: tekrar\: k\: :\: [/tex]
[tex]\: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: j=6\: \rightarrow\: Tedad\: tekrar\: k\: :\: 6 [/tex]
[tex]\: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: j=7\: \rightarrow\: Tedad\: tekrar\: k\: :\: [/tex]
[tex]\: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: j=8\: \rightarrow\: Tedad\: tekrar\: k\: :\: [/tex]
[tex]\: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: j=9\: \rightarrow\: Tedad\: tekrar\: k\: :\: 9[/tex]
.
.
.
پس جواب برابر [tex]\sum^n_{i=1}\sum_{j=1}^i(i\times j)[/tex] میشه. که برابر
[tex]\sum_{i=1}^ni\: \: \sum_{j=1}^ij\: =\: \sum_{i=1}^ni\times(\frac{i(i 1)}{2})\: [/tex] هستش.
که مرتبش میشه :[tex]\theta\: \: (n^4)[/tex]
(۲۷ اسفند ۱۳۹۴ ۰۱:۵۵ ق.ظ)IranianWizard نوشته شده توسط: سلام.
راه اول:
در صورتی حلقه k به تعداد j بار اجرا میشه که --> j بر i بخش پذیر باشه-->
پس در صورتی که j برابر : [tex]i\: or\: 2i\: or\: 3i\: or\: ...\: or\: ii[/tex] باشه،حلقه k به تعداد j بار اجرا میشه.
پس تعداد دفعات تکرار حلقه k برابر:
[tex]i\: \: 2i\: 3i\: \: ...\: \: ii[/tex] هستش. که برابر [tex]i\: \times\frac{i(i 1)}{2}\: =\frac{\: 1}{2}\: \times(i^3\: \: i^2)[/tex] هستش.
و با توجه با اینکه i از ۰ تا n هستش،پس جواب برابر :[tex]\frac{1}{2}\: \sum\: \: (i^3\: \: i^2)\: =\: \theta(n^4)[/tex] (سیگما از ۰ تا n)
پس جواب میشه [tex]\theta\: \: (n^4)[/tex]
راه دوم:
[tex]i=0\: \rightarrow\: -[/tex]
[tex]i=1\: \rightarrow\: \: j=1\: \rightarrow\: Tedad\: tekrar\: k\: :\: 1[/tex]
[tex]i=2\: \rightarrow\: \: j=1\: \rightarrow\: Tedad\: tekrar\: k\: :\: [/tex]
[tex]\: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: j=2\: \rightarrow\: Tedad\: tekrar\: k\: :\: 2[/tex]
[tex]\: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: j=3\: \rightarrow\: Tedad\: tekrar\: k\: :\: [/tex]
[tex]\: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: j=4\: \rightarrow\: Tedad\: tekrar\: k\: :\: 4[/tex]
[tex]i=3\: \rightarrow\: \: j=1\: \rightarrow\: Tedad\: tekrar\: k\: :\: [/tex]
[tex]\: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: j=2\: \rightarrow\: Tedad\: tekrar\: k\: :\: [/tex]
[tex]\: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: j=3\: \rightarrow\: Tedad\: tekrar\: k\: :\: 3 [/tex]
[tex]\: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: j=4\: \rightarrow\: Tedad\: tekrar\: k\: :\: [/tex]
[tex]\: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: j=5\: \rightarrow\: Tedad\: tekrar\: k\: :\: [/tex]
[tex]\: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: j=6\: \rightarrow\: Tedad\: tekrar\: k\: :\: 6 [/tex]
[tex]\: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: j=7\: \rightarrow\: Tedad\: tekrar\: k\: :\: [/tex]
[tex]\: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: j=8\: \rightarrow\: Tedad\: tekrar\: k\: :\: [/tex]
[tex]\: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: j=9\: \rightarrow\: Tedad\: tekrar\: k\: :\: 9[/tex]
.
.
.
پس جواب برابر [tex]\sum^n_{i=1}\sum_{j=1}^i(i\times j)[/tex] میشه. که برابر
[tex]\sum_{i=1}^ni\: \: \sum_{j=1}^ij\: =\: \sum_{i=1}^ni\times(\frac{i(i 1)}{2})\: [/tex] هستش.
که مرتبش میشه :[tex]\theta\: \: (n^4)[/tex]
سپاسات فراوان دوست عزیز