Loading...
DNikolov avatar DNikolov 12 Точки

Някой може ли да разпише как се получава сложността на следния фрагмент от код с вложени цикли?

Фрагмента е следния

sum=0
for(i=0;i<n-1;i++)
    for(j=i;j<n;j++)
        sum++;

Отговора е n(n-1)/2 , а примера е взет от „Програмиране = ++Алгоритми“. Въпроса е някой може ли да разпише подробно как се получава? Някава сума се намира най-вероятно. Ако да да включи и формулаата за сумата.

Тагове:
SStoyanov22 avatar SStoyanov22 39 Точки

Тъй като двата цикъла са зависими един от друг , не може просто да умножим сложностите на 2та цикъла, тъй като 2рия се изпълнява различен брой пъти, всеки път.

Вътрешният цикъл се изпълнява различен брой пъти, в зависимост от големината на променливата i , или иначе казано (n-i) пъти.
В зависимост от i, което може да бъде от 0 до n-2 включително, той се изпълнява съответно :
за i=0 --> от 0 до n-1 --> n-1 пъти,
за i=1 --> от 1 до n-1 --> n-2 пъти,
за i=2 --> от 2 до n-1 --> n-3 пъти,
....,
за i=n-2--> от n-2 до n-1 --> 1 път

 Сега може да сметнем сложността на 2та цикъла като съберем получените резултати:
n-1 + n-2 + n-3 + n-4 + .... + 1, което е Аритметична прогесия  и ако се приложи формулата за сума на  Аритметична прогресия се получава ((n-1)+1)*(n - 1)/2, което e след опростяване е равно на (n-1) * n / 2
 

6
29/06/2015 22:13:30
dim4o avatar dim4o 288 Точки

Аз все пак си мисля, че сложността в задачата не е (n - 1) * n/2, защото за i = 0 във втрешния цикъл имаме n стъпки, т.е. от 0 до n-1 включително и така стъпките намаляват, докато i = n-2 при което вътрешния цикъл ще се завърти 2 пъти. Т.е. имаме N + (N -1) +...+ 2 = (N + 2)(N - 1)/2, което би трябвало да е коректния отговор според мен.

1
dim4o avatar dim4o 288 Точки

 

Понеже сме писали почти едно и също обяснение с колегата  SStoyanov22 (кажи речи по едно и също време) редактирам моето, като само ще добавя, че ако отговорът трябва да е n(n-1)/2 тогава трябва да имаме сбора 1 + 2 + ... + n-1 = (n-1)n/2, т.е във вътрешния цикъл не трбва да имаш от i до n, а от i+1 до n. Друг вариант е ако вместо i=0 e i = 1 и пак имаш (n-1)n/2

2
29/06/2015 22:01:30
SStoyanov22 avatar SStoyanov22 39 Точки

Прав си колега, сега се поправих! Помислих, че символите &lt са за по- малко или равно :)

1
dim4o avatar dim4o 288 Точки

Да и аз се обърках ва началото, защотo беше кофти написано и не видях, че външния цикъл е до n-1, а не до n.

0
stiliyanmarkov avatar stiliyanmarkov 3 Точки

Здравейте, 
 

Според мен, отговора е верен, защото имаме сума на първите N-1 члена, или:

(n-1) + (n-2) + (n-3) .... + 2 + 1 + 0

Ако приложим формулата за аритметична прогресия:  n(n+1)/2 за нашия случай заместваме n със n-1 ще получим

(n-1)((n-1)+1)/2 => n(n-1)/2

2
stiliyanmarkov avatar stiliyanmarkov 3 Точки

Ако разпишем двата цикъла, ще започнем от n и за всяка стъпка на външния цикъл ще ходим n-1 или:

1. n-1

2. (n-1)-1

3. ((n-1)-1) -1

и т.н. затова за мен, това е  n-1 + ((n-1)-1) + (((n-1)-1)-1) => (n-1) + (n-2) + (n-3) .... + 2 + 1 + 0

0
DJZoning avatar DJZoning 85 Точки

Според мен отговора е n(n+1)/2-1, защото имаме n + (n-1) + (n-2) + ... + (n-(n-2))

Така както е външния цикъл ще се завърти n-1 пъти. При първата итерация на външния цикъл, вътрешния цикъл винаги ще се върти n пъти а в последната итерация на външния цикъл, вътрешния винаги ще се върти два пъти.

Ако вземем за пример следното:

for (int i = 0; i < n - 1; i++)
{
   for (int j = i; j < n; j++)
   {
      Console.Write("* ");
   }
   Console.WriteLine();
}

Изхода е следния --> Output

Това е като Triangular Numbers T(n) само, че без 1 понеже външния цикъл е до n-1 т.е. за всяка стойност на n ще получим triangular number - 1

2
30/06/2015 00:30:15
Можем ли да използваме бисквитки?
Ние използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Можете да се съгласите с всички или част от тях.
Назад
Функционални
Използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Използваме „сесийни“ бисквитки, за да Ви идентифицираме временно. Те се пазят само по време на активната употреба на услугите ни. След излизане от приложението, затваряне на браузъра или мобилното устройство, данните се трият. Използваме бисквитки, за да предоставим опцията „Запомни Ме“, която Ви позволява да използвате нашите услуги без да предоставяте потребителско име и парола. Допълнително е възможно да използваме бисквитки за да съхраняваме различни малки настройки, като избор на езика, позиции на менюта и персонализирано съдържание. Използваме бисквитки и за измерване на маркетинговите ни усилия.
Рекламни
Използваме бисквитки, за да измерваме маркетинг ефективността ни, броене на посещения, както и за проследяването дали дадено електронно писмо е било отворено.