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