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), поскольку она состоит из двух этапов:
- Получение минимального элемента, который, как вы указываете, является O (1), потому что он, как известно, находится наверху кучи.
- Удаление минимального элемента. Это O(log n), потому что оно включает перемещение последнего элемента из кучи в корень, а затем отсеивание его для перенастройки кучи.
Если вы просто хотите получить минимальный элемент, не удаляя его, тогда операция действительно O (1). Но всякий раз, когда вы хотите изменить кучу (и удаление первого элемента, безусловно, подходит), это операция O(log n).
Примечание Nitpickers: я понимаю аргумент, что вставка в минимальную кучу - это, в среднем, операция O (1). В то время как в некоторых ситуациях это может быть правдой, наихудшим случаем по-прежнему является O(log n). (Попробуйте вставить значения в кучу в обратном порядке. Каждая вставка - O(log n).)