Нахождение нижней и верхней границы сложности
Я хочу найти нижнюю и верхнюю границу сложности этого алгоритма
1: for all i=1 to n*n do
2: for all j=i to 2*i do
3: output “hello world”
4: end for
5: end for
Записав это как суммирование и упростив до
f(n) = 0.5*n^4 + 1.5*n^2
Кажется, что верхняя граница сложности - O (n ^ 4), поскольку 0,5 * n ^ 4 является наиболее значимым элементом.
Для оценки снизу сложности я использовал формулу
f(n) = Ω(g(n)) if f(n) >= c * g(n), where c > 0
и кажется, что нижняя граница равна Ω (n ^ 3) для 0 <c <1
Верны ли мои рассуждения в обоих случаях? Есть ли более простой способ найти Омегу? Спасибо за ваше время :)
Ответы 1
Я почти уверен, что сложность вашего кода статична, поэтому верхняя и нижняя границы равны.
edit: я знаю обозначения сложности из алгоритмы сортировки. Количество итераций зависит от того, как выполняется сортировка, и, конечно, от начального порядка списка. Алгоритмы сортировки обычно самые быстрые в уже отсортированных списках. Итак, есть лучший случай, где все отсортировано, и худший случай (некоторый беспорядок), который зависит от алгоритма. Некоторые алгоритмы будут бороться с просто перевернутыми списками, а другие - нет. Вот почему не существует идеального алгоритма сортировки. Вы можете выбрать лучшее для вашей ситуации.