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

У меня есть этот массив, который имеет свойство максимальной кучи. Временная сложность 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)

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

Источник

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

Источник

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

Источник

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

Источник

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

Источник
Другие вопросы по тегам