O(1) и O(log n), это одно и то же?

Возникает вопрос, задающий ли минимальный элемент из минимальной кучи время o (logn), я подумал, что это неверно, потому что требуется постоянное время, потому что минимальный элемент находится сверху. Но ответ верен, и объяснение преподавателя таково, что постоянное время также равно O(logn), это была проблема формулировки. Я довольно смущен. Итак, на практике, считаем ли мы постоянное время временем выполнения O(logn)?

3 ответа

Решение

Это правда, что все, что является O (1), является O (log n). Однако неверно, что все, что есть O (log n), есть O (1). O - верхняя граница, поэтому вы всегда можете использовать более быстро растущую функцию.

Думайте об этом так:

  • Микки Маус - это мышка
  • Все мыши являются млекопитающими
  • Следовательно, Микки Маус - млекопитающее
  • ... но "мыши" и "млекопитающие" не являются синонимами

Оказывается, что обозначение O является лишь верхней границей задачи. постоянное время может быть введено в любую запись O, потому что верхняя граница не имеет ограничений, может быть, даже вплоть до n!. Большая О запись не тета.

Извлечение минимального элемента из min-heap является операцией O(log n), поскольку она состоит из двух этапов:

  1. Получение минимального элемента, который, как вы указываете, является O (1), потому что он, как известно, находится наверху кучи.
  2. Удаление минимального элемента. Это O(log n), потому что оно включает перемещение последнего элемента из кучи в корень, а затем отсеивание его для перенастройки кучи.

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

Примечание Nitpickers: я понимаю аргумент, что вставка в минимальную кучу - это, в среднем, операция O (1). В то время как в некоторых ситуациях это может быть правдой, наихудшим случаем по-прежнему является O(log n). (Попробуйте вставить значения в кучу в обратном порядке. Каждая вставка - O(log n).)

Другие вопросы по тегам