Как считать сложность алгоритма?
Задумался вот о такой, казалось бы, простой вещи и понял, что у меня здесь пробел в знаниях. Что я имею ввиду когда говорю о подсчете сложности алгоритма? К примеру вы написали какую-то функцию, которая: сортирует два массива, проходится по ним циклом составляя на их основе некий новый массив и в конце, прежде чем вернуть полученный массив, реверсирует его - какая в итоге будет сложность алгоритма? Я знаю что операция сортировки имеет логарифмическую сложность, а цикл по элементам и реверс - линейную. Но какова сложность самой функции в результате? Она будет равна самой медленной операции (в таком случае это будет линейная сложность) или это будет какой-то новый вариант, где мы просто сложим все 4 имеющихся сложности (вроде 2 log_comp + 2 linear_comp)?
Заранее спасибо!
Ответы (1 шт):
Сложность алгоритма расчистывается показывая относительный класс. Например если сравнивать O(n^2) и O(n), то деление их друг на друга приведёт к бесконечному увеличению :
и это значит, что эти скорости отличаются на порядок.
А если добавить к логарифмической сложности одну линейную, то принципиально отношение отличаться не будет.
если это добавление не слишком громоздкое. Например при маленьких значениях n может быть увеличено время на треть, а при больших уже только +10%. Сложность будет O(n*Log[n]).
Если например добавить n^(3/2) то узнать что из них перевесит можно опять делением.
Бесконечность означает, что при увеличении количества n степень n^(3/2) будет намного больше чем логарифм n*Log[n]. Сложность будет O(n^(3/2)).
Если отношение в скорости отличаются на конечное число, например в два раза, то это константное соотношение на класс скорости не влияет.