Что значит удовлетворять O (f (N)) для данного уравнения f (N)?

Это единственный вопрос в моем последнем обзоре, в котором я все еще не уверен. Я разобрался со всеми остальными 74, но этот полностью меня озадачил. Я думаю, что это как-то связано с поиском C и k, но я не помню, как это сделать или что это вообще значит … и я, возможно, даже не на правильном пути.

Вопрос, с которым я сталкиваюсь: «Какое минимальное приемлемое значение для N такое, что определение для O(f(N)) удовлетворен для функции члена Heap::Insert(int v)

Код для Heap :: Insert (int v) выглядит следующим образом:

void Insert(int v)
{
if (IsFull()) return;
int p=++count;

while (H[p/2] > v) {
H[p] = H[p/2];
p/= 2;
}
H[p] = v;
}

Возможные ответы: 32, 64, 128, 256,

Я в полном недоумении и должен сдать этот экзамен утром. Помощь будет очень цениться.

-1

Решение

Я признаю, что вопрос довольно неясен, но я постараюсь дать разумное объяснение.

Если мы позвоним f(N) временная сложность операции, выполняемой вашим кодом в зависимости от количества элементов в куче, профессор хотел, чтобы вы помнили, что f(N) = O(log(N)) для вставки двоичной кучи, то есть O(h), где h это высота кучи, и мы предполагаем, что она завершена (помните, как работает куча и что она может быть представлена ​​в виде двоичного дерева). Таким образом, вы должны попробовать эти четыре значения Nmin и найти самый маленький, который удовлетворяет определению, то есть тот, для которого

f(n) <= k*log(N)

Для каждого N >= Nmin и по крайней мере k, Я бы дал вам детали для расчета f(N) если бы только ваш код делал то, что профессор или вы ожидали от него.

Примечание: я бы очень хотел сделать рендеринг LaTeX поверх вопросов переполнения стека! Как на математике

1

Другие решения

Других решений пока нет …

По вопросам рекламы ammmcru@yandex.ru
Adblock
detector