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

У меня есть этот массив, который имеет свойство max heap. Сложность время deleteMax составляет o(Фремонт, Калифорния). Если приведенный ниже код будет повторяться только 7 раз, какова будет временная сложность приведенного ниже кода (big 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)

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

4 3
data-structures heap time-complexity

4 ответа:

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

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

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(зарегистрируйте N). Просто потому, что нет входных данных, изменяющих количество циклов.

5

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

1

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

0

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

0