Фрагмента е следния
sum=0
for(i=0;i<n-1;i++)
for(j=i;j<n;j++)
sum++;
Отговора е n(n-1)/2 , а примера е взет от „Програмиране = ++Алгоритми“. Въпроса е някой може ли да разпише подробно как се получава? Някава сума се намира най-вероятно. Ако да да включи и формулаата за сумата.
Тъй като двата цикъла са зависими един от друг , не може просто да умножим сложностите на 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
Понеже сме писали почти едно и също обяснение с колегата 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
Прав си колега, сега се поправих! Помислих, че символите < са за по- малко или равно :)
Да и аз се обърках ва началото, защотo беше кофти написано и не видях, че външния цикъл е до n-1, а не до n.
Здравейте,
Според мен, отговора е верен, защото имаме сума на първите 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
Ако разпишем двата цикъла, ще започнем от 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
Според мен отговора е 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
Аз все пак си мисля, че сложността в задачата не е (n - 1) * n/2, защото за i = 0 във втрешния цикъл имаме n стъпки, т.е. от 0 до n-1 включително и така стъпките намаляват, докато i = n-2 при което вътрешния цикъл ще се завърти 2 пъти. Т.е. имаме N + (N -1) +...+ 2 = (N + 2)(N - 1)/2, което би трябвало да е коректния отговор според мен.