Это единственный вопрос в моем последнем обзоре, в котором я все еще не уверен. Я разобрался со всеми остальными 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
,
Я в полном недоумении и должен сдать этот экзамен утром. Помощь будет очень цениться.
Я признаю, что вопрос довольно неясен, но я постараюсь дать разумное объяснение.
Если мы позвоним f(N)
временная сложность операции, выполняемой вашим кодом в зависимости от количества элементов в куче, профессор хотел, чтобы вы помнили, что f(N) = O(log(N))
для вставки двоичной кучи, то есть O(h)
, где h
это высота кучи, и мы предполагаем, что она завершена (помните, как работает куча и что она может быть представлена в виде двоичного дерева). Таким образом, вы должны попробовать эти четыре значения Nmin
и найти самый маленький, который удовлетворяет определению, то есть тот, для которого
f(n) <= k*log(N)
Для каждого N >= Nmin
и по крайней мере k
, Я бы дал вам детали для расчета f(N)
если бы только ваш код делал то, что профессор или вы ожидали от него.
Примечание: я бы очень хотел сделать рендеринг LaTeX поверх вопросов переполнения стека! Как на математике
Других решений пока нет …