Я действительно путают о времени

Question

макетов Я понимаю, что время алгоритм, в T(n) может быть ограничена O(g(n)) по определению:

T(n) is O(g(n)) iff there is a c > 0, n0 > 0, such that for all n >= n0: 

для каждого входа размера n, А принимает в большинстве c * g(n) шагов. T(n) - это время, которое является самым длинным из всех входов размера n.

Однако я не понимаю, является ли определение для Ω(g(n)). Определение состоит в том, что для некоторый ввод размера n, A занимает не менее c * g(n) шагов.

Но если это определение для Ω, тогда я не могу найти нижнюю границу для любого альгорта, который совпадает с верхней границей? Например, если сортировка в худшем случае принимает O(nlogn), тогда я не смогу легко показать Ω(nlogn), а также посмотреть, как должен быть хотя бы один плохой ввод для любого размера n, который мог бы принимать nlogn шагов? Предположим, что мы говорим о heapsort. Я действительно не уверен, что мне здесь не хватает, потому что всякий раз, когда меня обучают новому алгоритму, время для определенного метода равно либо Ɵ(g(n)) or O(g(n)), но и не объясняется, почему это либо Ɵ or O.

Надеюсь, я сказал, что я был достаточно ясен, если не спрашиваю про то, что вы неправильно поняли. Мне действительно нужно, чтобы эта путаница прояснилась. Спасибо.

Answer 1

Определение, что я знаком с в том, что Т (п) Ω (г (п)), если в течение некоторого n0, для всех n>n0, T(n) >= g(n)*k для некоторого k.

Тогда что-то есть Θ (n) если оно равно O (g (n)) и Ω (g (n)).

Answer 2

O является верхней границей, что означает, что мы знаем, что алгоритм O(n lg n) занимает асимптотически не более постоянного времени. n lg n шагов в худшем случае.

Ω является нижней границей, а это означает, что мы знаем, что это не возможно для Ω(n lg n) алгоритма взять асимптотический меньше, чем n lg n шагов в худшем случае.

Ɵ является плотно связаны: например, если алгоритм Ɵ(n lg n) то мы знаем, как это и O(n lg n) (так, по крайней мере так быстро, как n lg n) и Ω(n lg n) (так что мы не знаем, что это не быстрее, чем n lg n).

Причина, по которой ваш аргумент является ошибочным, заключается в том, что вы на самом деле предполагаете, что знаете Ɵ(n lg n), а не только O(n lg n).

Например, мы знаем, что существует общая привязка к сопоставлениям Ω(n lg n). Как только мы доказали O(n lg n) для mergesort, это означает, что mergesort - Ɵ(n lg n). Обратите внимание, что mergesort является такжеO(n^2), потому что это no slower than n^2. (Это не то, как люди обычно описывают это, но это то, что означает формальное обозначение.)

Для некоторых алгоритмов мы не знаем плотных границ; общий 3SUM problem в простых моделях вычислений известен как Ω(n lg n), потому что его можно использовать для выполнения сортировки, но у нас есть только алгоритмы Ɵ(n^2). Наилучший алгоритм для проблемы находится между n lg n и n^2; мы можем сказать, что это O(n^2) и Ω(n lg n), но мы не знаем Ɵ.

Там также o(f), что означает строго меньше f и ω(f), что означает строго больше f.