@asault_ceko

Как определить сложность алгоритма?

Наткнулся на такой алгоритм сортировки. Это микс выбора и обмена. Мне интересно узнать, какая у него сложность. Я уже нашел K1 и K2 и думаю, что здесь будет O(n^3), но не уверен, потому что может здесь O(n^2)? Просто дальше трудно и не могу уже придумать зависимость.
K1 = [n/2]; 
K2 = [(n^2)/4];

661da4ba5f913293963801.jpeg
  • Вопрос задан
  • 122 просмотра
Пригласить эксперта
Ответы на вопрос 3
Может эта статья вам поможет
Ответ написан
Комментировать
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Внутренние циклы выполняют суммарно максимум 8(r-l-1) операций. На каждой итерации внешнего цикла r-l уменьшается на 2. Т.е. всего операций будет 8(n-2)+8(n-4)+8(n-6)...

Можете эту арифметическую прогрессию подсчитать и оценить?
Ответ написан
Комментировать
@Mercury13
Программист на «си с крестами» и не только
У нас два вложенных цикла, каждый порядка n.
Значит, O(n)·O(n) = O(n²), если не докажем меньше.
Не докажем, там обычная арифметическая прогрессия, которая что-то вроде n(n—1)/2.
Ответ написан
Комментировать
Ваш ответ на вопрос

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

Похожие вопросы