Временная сложность или большое О кода

У меня есть этот массив с максимальным свойством кучи. Временная сложность deleteMax равна O(logn). Если приведенный ниже код будет повторяться всего 7 раз, какова будет временная сложность приведенного ниже кода (большой O)?

int heap_size = 15;
int i, value, heap_array[]; // array is in the form of max heap
....
for(i = 0; i < 7; i++){ // iterates seven times
    value = deleteMax(heap_array);
    printf("%d ", value);
}

У меня в голове два решения. Во-первых: временная сложность равна O(7 * logn) или просто O(logn).

Тогда второй - O (1/2 * n * logn) или O (nlogn), поскольку 1/2 - это просто константа, и я предполагаю, что, поскольку число итераций равно 7, что почти такое же, как половина heap_size, я могу игнорировать 1/2. Таким образом, O(nlogn)

Какой из них будет правильным?


c data-structures time-complexity heap binary-heap
person labyrinthdeux    schedule 12.04.2017    source источник
comment
Если размер кучи всегда равен 15, здесь у вас постоянная временная сложность. О (1). Это не функция ввода, потому что ввода нет.   -  person xiaofeng.li    schedule 12.04.2017
comment
@LukeLee Я думаю, вам нужно учитывать функцию deleteMax внутри цикла for - O (logn), а также количество итераций в цикле for? Что меня смущает, так это то, что цикл for будет повторять только до 7 элементов, а не весь размер кучи.   -  person labyrinthdeux    schedule 12.04.2017
comment
Ну ты неудачный пример подобрала. Если цикл for выполняется n/2 раз, это более интересно.   -  person xiaofeng.li    schedule 12.04.2017
comment
Это может быть то, что вы на самом деле спросили.   -  person xiaofeng.li    schedule 12.04.2017

Ответы (4)


arrow_upward
5
arrow_downward

Вообще бессмысленно говорить о сложности, когда число фиксировано (то есть постоянно). Вся цель нотации состоит в том, чтобы оценить, как изменяется время выполнения при изменении числа. Постоянное количество циклов никогда не изменит ни время выполнения, ни сложность. Если вы измените количество циклов на другое постоянное значение, это изменит время выполнения, но сложность останется прежней.

Типичное использование — вычисление сложности функции, чтобы дать пользователю функции представление о том, как изменяется время выполнения, когда пользователь изменяет какое-либо входное значение. Пример:

void foo()                 // Pointless to talk about complexity as there is no input

void foo(int x)            // Complexity tells you how execution time change 
                           // when you change x

void foo(char* someString) // Complexity tells you how execution time change 
                           // when you change the length of someString

Примечание. Сложность никогда не говорит вам фактическое время выполнения! Только то, как изменяется время выполнения при изменении некоторого ввода.

Итак, в вашем случае сложность по-прежнему определяется deleteMax, т. е. по-прежнему O (log n). Просто потому, что нет ввода, изменяющего количество петель.

person 4386427    schedule 12.04.2017
comment
Итак, если я сделаю от i ‹ 7 до i ‹ 20 (при условии, что это безошибочно), временная сложность все равно будет O(logn), поскольку она не зависит от размера данных? Я прав с этим? Кстати, ответ принят. Спасибо - person labyrinthdeux; 12.04.2017
comment
@labyrinthdeux Верно. Изменение с 7 на 20 не влияет на сложность. Нотация не предназначена для указания того, сколько времени требуется для выполнения фрагмента кода. Обозначение сообщает вам, как изменяется время выполнения, когда вы что-то меняете, например. длина массива, который вы даете в качестве входных данных - person 4386427; 12.04.2017
comment
@labyrinthdeux - Но если вы сделали ограничение цикла зависящим от чего-то, например. i < someInputValue, то сложность изменится. - person 4386427; 12.04.2017
comment
@ 4386427: Я бы добавил, что сложность говорит вам, как изменяется время выполнения при изменении некоторых входных данных, для больших входных данных. Это потому, что мы сохраняем только доминирующий термин. Если время выполнения определяется как T(n) = n^2 + 1000*n, сложность составляет O(n^2), но увеличение будет почти линейным для малых ns. Только для больших ns оно становится (почти) квадратичным. - person Thomas Padron-McCarthy; 12.04.2017

arrow_upward
1
arrow_downward

Если цикл выполняется всего 7 раз, то сложность равна O(1). Это связано с тем, что цикл не зависит от размера данных и всегда будет выполняться за постоянное время.

person Archmede    schedule 12.04.2017
comment
Итак, если я сделаю от i ‹ 7 до i ‹ 20 (при условии, что это безошибочно), временная сложность все равно будет O(logn), поскольку она не зависит от размера данных? Я прав с этим? - person labyrinthdeux; 12.04.2017
comment
@Archmede: если цикл выполняется фиксированное количество раз, то сложность будет такой же, как и у deleteMax, которая была заявлена ​​как O (log n). - person Thomas Padron-McCarthy; 12.04.2017

arrow_upward
0
arrow_downward

Здесь и размер кучи, и количество запусков цикла являются постоянными. Таким образом, код будет иметь временную сложность O(1), то есть постоянную временную сложность.

person vantony    schedule 12.04.2017

arrow_upward
0
arrow_downward

Я думаю, что вы опирались на алгоритм сортировки кучи, и я уверен, что сложность составляет O (nlogn).

person slzy    schedule 12.04.2017