Что я имею ввиду когда говорю о подсчете сложности алгоритма? К примеру вы написали какую-то функцию, которая: сортирует два массива, проходится по ним циклом составляя на их основе некий новый массив и в конце, прежде чем вернуть полученный массив, реверсирует его - какая в итоге будет сложность алгоритма? Я знаю что операция сортировки имеет логарифмическую сложность, а цикл по элементам и реверс - линейную. Но какова сложность самой функции в результате? Она будет равна самой медленной операции (в таком случае это будет линейная сложность) или это будет какой-то новый вариант, где мы просто сложим все 4 имеющихся сложности (вроде 2 log_comp + 2 linear_comp)?
-
5если мы говорим о O(n), то сложность будет соотвествовать самой седленной части вашего описания, то есть сложность будет линейно-логарифмическая или nLog(n)– tym3216724 мар 2021 в 20:59
-
1ru.wikipedia.org/wiki/…– tym3216724 мар 2021 в 21:03
-
Сложность, которая считается от О большое часто расходится с тем, что будет лучше на практике, потому что этот метод априори работает с бесконечностью.– megorit25 мар 2021 в 6:39
-
1Сдается мне, что в вашем случае это O(n log n + m log m) - две сортировки.– Mikhailo26 мар 2021 в 13:41
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)).
Если отношение в скорости отличаются на конечное число, например в два раза, то это константное соотношение на класс скорости не влияет.