Нахождение нижней и верхней границы сложности

Question

Я хочу найти нижнюю и верхнюю границу сложности этого алгоритма

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

Верны ли мои рассуждения в обоих случаях? Есть ли более простой способ найти омегу? Спасибо за ваше время:)

Answer 1

Я почти уверен, что сложность вашего кода статична, поэтому верхняя и нижняя границы равны.

edit: я знаю обозначения сложности из алгоритмов сортировки . Количество итераций зависит от того, как выполняется сортировка, и, конечно, от начального порядка списка. Алгоритмы сортировки обычно самые быстрые в уже отсортированных списках. Таким образом, есть лучший случай , где все отсортировано, и худший случай (некоторое расстройство), которое зависит от алгоритма. Некоторые алгоритмы будут бороться с просто перевернутыми списками, а другие нет. Вот почему не существует идеального алгоритма сортировки. Вы можете выбрать лучшее для вашей ситуации.