@KuzmenkoArtem

Какая сложность алгоритма (относительно n)?

Все привет!
Кто знает как описать сложность этого алгоритма?

k = 0
for(i = n / 2; i < n; i++)
    for(j = 0; j < i; j++)
        k = k + n / 2


Буду благодарен за краткое объяснение, но можно и просто результат, если что потом разберусь, с решением будет проще
Заранее спасибо!

UPD: Нашел варианты ответов
0(n)
0(n/2)
O (n log(n))
O(n^2)
  • Вопрос задан
  • 148 просмотров
Решения вопроса 2
@Mercury13
Программист на «си с крестами» и не только
O(n²), разумеется.
Первый цикл выполняется O(n) раз, и второй O(n). Так что O(n²).
Если быть точнее, те итерации, которые выполнятся,— это трапеция на квадрате n×n, никакого тебе O(n), O(n log n) и подобного не будет.
Кстати, запись O(n/2) и O(n²/2) не имеет особого смысла — само определение символов Ландау говорит, что разница в константу не играет роли. По той же причине пишут O(n log n), не указывая, по какому основанию логарифм.

UPD2. Запись O(n²) означает: «не превышает cn² при стремлении n→∞». Так что всё, что O(n), одновременно и O(n²). И «никакого тебе O(n)» означает, что оценку n² мы улучшить не можем.
Ответ написан
Конечно же O(n^2). Нотация O-большое съедает все константы.

Почему квадратичность? Потому что в каждом проходе внешнего цикла запускается проход внутреннего цикла, а количество итераций в каждом цикле зависит от n.
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы