Как оценить лучшие, худшие и средние случаи для сложности времени?

Question

как мы можем определить, является ли сложность времени получения для алгоритма наилучшим или худшим случаем или средним случаем?Например, если мы получим сложность времени как t (n) = 2n ^ 2 + 3n -1, как оценить лучшие или худшие или средние случаи?

Answer 1

первое примечание: t (n) = 2n ^ 2 + 3n -1 всегда будет большой O (n ^ 2) в худшем, лучшем и среднем случае.

Вв некоторых случаях сложность зависит от ввода вашего алгоритма, в этих случаях обычно люди вычисляют сложность в худшем случае.

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

Посмотрите на этот пост более подробную информацию об анализе среднего случая и амортизированном анализе.

Разница между средним случаем и амортизированным анализом

и статьи в Википедии:

• средняя сложность дела
• амортизированный анализ

Answer 2

Вы можете сказать это, только внимательно изучив алгоритм.

Если вы знаете, что точно t (n) = 2n ^ 2 + 3n-1, то t (n) = O (n ^ 2), и это лучшее, худшее и, следовательно, среднее сложность времени.

Answer 3

>> Бастель:

Если вы обнаружите сложность Best case , то вы проверяете изображение и следующее утверждение.

T(n)= c1n+c2(n-1)+c4(n-1)+c5(n-1)+c8(n-1)
      (c1+c2+c5+c8)n-(c2+c4+c5+c6)

Максимальная мощность из n равна 1 , поэтому мы говорим, что Лучший вариант Сложность - сортировка вставкой O (п) .

>> Худший случай:

Если вы находите Худший случай Сложность, тогда вы проверяете изображение и следующее утверждение.

T(n)= c1n+c2(n-1)+c4(n-1)+c5(n(n+1)/2)+c6(n(n-1)/2)+c7(n(n-1)/2)+c8(n-1)
      (c5/2 + C6/2 +C7/2)n^2 +(c1+c2+c4+ c5/2 -C6/2 -C7/2+ c8)

Максимальная мощность из n равна 2 , поэтому мы говорим, что Лучший вариант Сложность - сортировка вставкой O (п ^ 2) .

Answer 4

Это упрощает до O (2n ^ 2) или просто O (n ^ 2). Вы удаляете все остальные элементы, потому что это упрощает.

Это известно как обозначение Big O. Это просто худшее время. Все остальные по большей части не имеют значения.