Худший случай против O (n)

Question

Есть ли разница между утверждением "Время выполнения алгоритма A в худшем случае" и "Время выполнения алгоритма A равно O (n)"?

Что я думаю, что "разницы нет", потому чтонаихудший случай - это пиковое время работы функции, O (n) означает, что функция «ограничена».Оба дают одно и то же значение.

Надеюсь, моя логика верна.

Answer 1

Есть разница.

Алгоритм O (f) не является точным: вы должны сказать, что alogirthm - это O (f) в его лучшем / худшем / среднем случае. Вы можете сказать, что O (f), когда лучшие, худшие и средние значения совпадают, но это не так часто.

Answer 2

Время выполнения как абсолютная мера, как правило, менее важно, чем , как увеличивается это время, когда вы добавляете больше данных . Например, алгоритм, который всегда занимает 5 секунд для обработки 100 элементов, 10 секунд для обработки 200 элементов и т. Д., Называется O (N), поскольку время выполнения линейно увеличивается с размером набора данных. Если второму алгоритму потребовалось 5 * 5 = 25 секунд для обработки этих 200 элементов, его можно классифицировать как O (N ^ 2). Здесь нет «пикового времени работы», поскольку время работы всегда увеличивается, когда вы добавляете больше данных.

На самом деле, большой O - это верхняя граница - так что вы могли бы сказать, что первым алгоритмом был также O (N ^ 2) (если N - верхняя граница, N * N выше и, следовательно, также верхняя граница, хотя и более свободный). Общие обозначения для обозначения других границ включают Ω (омега, нижняя граница) и Θ (тета, одновременная нижняя и верхняя граница).

Некоторые алгоритмы (например, Quicksort) демонстрируют различное поведение в зависимости от данных, которые ему передаются - следовательно, наихудшим случаем является O (N ^ 2), даже если он обычно ведет себя так, как если бы он был O (N log N).

Answer 3

Я согласен с вашим мнением, но есть распространенные алгоритмы (например, быстрая сортировка), которые имеют ожидаемое время намного лучше, чем их худшее время.Вы можете утверждать, что быстрая сортировка является O (N ^ 2) наихудшим случаем, но вы все равно ожидаете, что она будет O (N * log N) почти всегда (по крайней мере, для хорошей реализации).

Это также усложняется салгоритмы, которые амортизировали поведение.Вы можете получить O (N) или O (log N) для одной конкретной операции, но многие операции подряд всегда будут O (1) в амортизированном смысле.Хорошие примеры в этой категории - Splay-деревья и Finger-деревья.

Answer 4

Существует огромная разница между этими строками слов. «Наихудшее время выполнения Алгоритма А» - это существительное предложение, оно не делает никаких заявлений вообще. «Время выполнения алгоритма A - это O (n)» - это предложение, рассказывающее нам что-то об A.