Анализ сорта оболочки

Question

Я читаю книгу об алгоритмах, в которой упоминается анализ алгоритма сортировки оболочки, как показано ниже:

Наихудшее время работы Shellsort с использованием приращений Shell - Theta (n квадрат).

Для доказательства требуется не только верхняя граница наихудшего случая время работы, но также показывает, что существует некоторый вклад, который фактически занимает нижнюю границу как Omeaga (n квадрат) время, чтобы бежать. Мы доказываем сначала нижнюю границу, построив плохой случай.

Мой вопрос выше:

1. почему автор упоминает плохой случай, чтобы проверить нижнюю границу? Я учил, чтобы получить более низкую оценку, мы должны взять лучший случай, Просьба уточнить выше.

Спасибо!

Answer 1

Чтобы показать, что что-то есть Theta(f(n)), нужно показать как верхнюю, так и нижнюю границу, что и делает текст.

Утверждение, что "время наихудшего случая is Theta (n квадрат) "требует, чтобы один продемонстрировал верхнюю и нижнюю границы для указанного наихудшего времени .

Аналогично, утверждение о среднем * case время Тета (f (n)) потребует двух границ для среднего случая времени.

и т. д.

As @ Patrick87кратко говоря:

граница ортогональна падежу.

Answer 2

Тета является ограничивающим ограничением (как верхним, так и нижним).Чтобы показать, что алгоритм имеет время выполнения Theta (f (n)), вы должны установить две вещи:

1) в худшем случае алгоритм выполняется за время O (f (n)) для всех случаев [сложность наихудшего случая]

2) Алгоритм должен занимать время Omega (f (n)) [есть реальные примеры, которые встречаются в наихудшем сценарии]

Вы устанавливаете вторую часть, находяплохие случаи для алгоритма.

Answer 3

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

Тета-запись требует от вас установить верхнюю границу и нижняя граница.