Определение сложности алгоритма в худшем случае

Question

Может кто-нибудь объяснить мне, как можно определить сложность алгоритма в худшем случае. Я знаю, что нам нужно использовать уравнение W (n) = max {t (I) | I элемент D), где D - множество входов размера n. Подсчитать ли я количество операций, выполненных для каждого элемента I, и затем взять его максимум? Какой простой способ сделать это?

Answer 1

Начиная с уравнения, мы думаем об этом немного задом наперед. Что вас действительно волнует, так это масштабируемость или то, что она собирается делать, когда вы увеличиваете размер ввода.

Если у вас, например, просто цикл, у вас есть O (n) алгоритм временной сложности. Если у вас есть цикл внутри другого цикла, он становится O (n ^ 2), потому что теперь он должен сделать n ^ 2 много вещей для любого размера n ввода.

Когда вы говорите о худшем случае, вы обычно говорите о недетерминированных алгоритмах, где у вас может быть цикл, который может преждевременно остановиться. Для этого вам нужно предположить худшее и сделать вид, что цикл остановится как можно позже. Так что если у нас есть:

для (int i = 0; i .5) j = n; } }

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

Answer 2

Это уравнение является скорее определением, чем алгоритмом.

Заинтересован ли данный алгоритм в чем-либо, кроме размера входных данных? Если нет, то вычисление W (n) "просто".

Если это так, попробуйте придумать патологический вклад. Например, при быстрой сортировке может быть довольно очевидно, что отсортированный ввод является патологическим, и вы можете сделать некоторые подсчеты, чтобы увидеть, что он принимает O (n ^ 2) шагов. В этот момент вы можете либо

1. Утверждают, что ваш вклад "максимально" патологический
2. Выставить соответствующую верхнюю границу времени выполнения на любом входе

Пример # 1:

Каждый проход быстрой сортировки устанавливает точку поворота в нужном месте, а затем повторяется на двух частях. ( handwave alert ) В худшем случае остальная часть массива должна располагаться с одной стороны оси. Сортированный вход достигает этого.

Пример # 2:

Каждый проход быстрой сортировки ставит точку поворота в правильном месте, поэтому не более O (n) проходов. Каждый проход требует не более O (n) работы. Таким образом, никакой ввод не может привести к тому, что быстрая сортировка займет больше, чем O (n ^ 2).

В этом случае # 2 намного проще.