Это O(n) или O(n*logn) из кода ниже:алгоритмическая сложность этого вложенного цикла
for(int j=n, int sum = 0; j>0 ; j--)
for(int k=j; k >0; k--) sum++;
Список итераций:
j = 5: k = 5, 4, 3, 2, 1
j = 4: k = 4, 3, 2, 1,
j = 3: k = 3, 2, 1
j = 2: k = 2, 1
j = 1: k = 1
Мы имеем 15 итераций в общей сложности. Но, если это O(n), то должно быть только 5 итераций.
И если это O(n*logn) ответ будет только вокруг 11-12 итераций.
Это O(n^2). Зачем? Ну это займет:
Посмотрите, что n = 5 количество расчетов я 15 на деле. С другой стороны, для n=100 это будет 5050, который далеко от 100log100, который составляет около 460.
Согласно Википедии:
Big O обозначение является математическим выражением, которое описывает предельное поведение функции, когда аргумент стремится к определенному значению или бесконечности. Он является членом семейства обозначений, изобретенных Полом Бахманом, Эдмундом Ландау и другими, в совокупности называемыми обозначениями Бахмана-Ландау или асимптотической нотации.
Это не так, как работает Big O. Вы не можете посмотреть количество итераций для определенного n и определить алгоритмическую сложность, вам нужно проанализировать количество итераций для общих значений n. – interjay
Мир создан не только из алгоритмов O (n) и O (n Log n)! –
Подсказка: какая область треугольника? [Не шучу] –