Този код O(n) или O(logn) ли е?

Проверява само цикъла for 1/3n пъти, така че все още е технически линеен, предполагам? Въпреки това наистина не разбирам защо не би било O(logn), защото много пъти код с O(logn) време за изпълнение завършва с проверка около 1/3n. O(logn) винаги ли разделя опциите на 2 всеки път?

int a = 0;
for (int i = 0; i < n; i = i+3)
    a = a+i;

java big-o
person user3251142    schedule 19.03.2014    source източник
comment
Когато удвоите n, броят на изпълнението на вашия цикъл удвоява ли се? Или добавя константа?   -  person hobbs    schedule 19.03.2014
comment
Вашият пример е O(n); защото е линеен. Помислете за нещо като двоично търсене за логаритмичен алгоритъм.   -  person Elliott Frisch    schedule 19.03.2014
comment
това има смисъл, hobbs. благодаря, че го изясни   -  person user3251142    schedule 19.03.2014
comment
Малка заядка, но ; след i = i + 3 е синтактична грешка.   -  person ajb    schedule 19.03.2014
comment
Лошото ми, не исках да пиша това   -  person user3251142    schedule 19.03.2014

Отговори (4)


arrow_upward
2
arrow_downward

вашият код има сложност O(n), O(n)/3 == a * O(n) == O(n)

person user902383    schedule 19.03.2014

arrow_upward
2
arrow_downward

При анализа на времевата сложност постоянните фактори нямат значение. Можете да направите 1 000 000 операции на цикъл и пак ще бъде O(n). Тъй като константата 1/3 няма значение, тя все още е O(n). Ако имате n при 1 000 000, тогава 1/3 от n ще бъде много по-голямо от log n.

От запис в Уикипедия относно нотацията Big-O:

Нека k е константа. Тогава:

O(kg) = O(g) if k is nonzero.
person rgettman    schedule 19.03.2014
comment
rgettman, имам един въпрос. Ами ако вътре в цикъла for имаме n = n-2; след a = a+i;? Какво би било Big-O в този случай? - person user3251142; 19.03.2014
comment
@user3251142 Все още O(n). Броят на итерациите ще бъде около n/5 вместо n/3 (като се използва първоначалната стойност на n). Предполагам, че ще добавите къдрави скоби, така че n=n-2 да бъде част от цикъла. - person ajb; 19.03.2014
comment
Запитайте се дали броят на повторенията в цикъла for все още ще бъде пропорционален на първоначалната стойност на n. - person rgettman; 19.03.2014
comment
добре, ще бъде (n-2*c)/3 или нещо подобно... нали? което, ако удвоите n, времето за работа няма да се удвои по същия начин... ще бъде ли? - person user3251142; 19.03.2014
comment
@user3251142 Всички тези 2*c и /3 неща са операции с константи. Все още е O(n). Начинът да направите такъв цикъл O(log n) е или да разделите n на константа на всеки цикъл, или да умножите i по константа на всеки цикъл. - person rgettman; 19.03.2014
comment
какво ще кажете, ако вътре в цикъла for имах това: if (n%3 == 2) n = 9;. Ако n имаше остатък 2, кодът щеше да приключи много бързо! Това не създава ли огромни различия? - person user3251142; 19.03.2014
comment
това не е ли едновременно O(n) и O(9)? - person user3251142; 19.03.2014
comment
Знам, че отговорът вероятно е O(n), но как може да бъде, ако има възможност за прекратяване на цикъла толкова бързо? - person user3251142; 19.03.2014
comment
@user3251142 Зависи какъв въпрос се задава. Ако въпросът е каква е горната граница, тогава тя все още е O(n), защото цикълът може да се изпълни k*n пъти (за някаква константа k). Ако това е средното време, вашият цикъл ще бъде постоянен в 1/3 от случаите и O(n) в останалите 2/3, така че средното време ще бъде 2/3 от това, което би било без if, но това все още е постоянен множител, така че средната стойност все още е O(n). Страхувам се, че изчисляването на дисперсията или стандартното отклонение е излишно. - person ajb; 19.03.2014

arrow_upward
1
arrow_downward

Това е ред на n O(n), а не O(logn). Това е така, защото времето за изпълнение се увеличава линейно с увеличаването на n

За повече информация погледнете тази графика и се надяваме, че ще разберете защо не е регистрирана https://www.cs.auckland.ac.nz/software/AlgAnim/fig/log_graph.gif

person pizzaEatingGuy    schedule 19.03.2014

arrow_upward
1
arrow_downward

Работното време е O(n) (в единица мярка за сложност).

person Codor    schedule 19.03.2014