@12LiCaNtRoP12

Какое будет время работы алгоритма?

По моим подсчетам количество итераций в цикле в алгоритме равно числу, оооочень похожему на число Фибоначи от длины массива. Если например будет массив с 4 элементами, количество итераций в цикле будет равно: 0+1=1, 1+2=3, 3+3=6, где во всех выражениях первое слагаемое - количество итерация на данный момент, а второе - индекс от 1 до (длинны массива)-1. Я не знаю, может подобному считыванию есть название, но мой вопрос: как выразить время работы этого алгоритма в О-большой? Также позже я посчитал, что количество итераций приблизительно равно (длина массива в квадрате)/2, можно ли таким образом записать, что время работы алгоритма равно О(N^2/2)?
  • Вопрос задан
  • 244 просмотра
Решения вопроса 1
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Проверка на малых числах не всегда работает. там фибоначи, квадрат и черт знает что похожи.

Если у вас там что-то вроде for "i=1...n do for j = i..n do" или каике-то еще 2 вложенных цикла, где внутренняя переменная бежит от или до внешней переменной, то точное количество итераций будет n(n+1)/2, что есть O(N^2).

Ваше последнее суждение - верно.
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

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

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