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

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

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

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