Всем привет!
Хочется наконец-то разобраться с подсчетом сложности алгоритмов, особенно, не всегда ясно, как оценить сложность по памяти.
Можете посоветовать какие-нибудь статьи или книги на эту тему?
Если в двух словах, то для начала надо бы познакомиться с О - семантикой, но это наживное.
Запомни, что есть след. базовые алгоритмические сложности
1. О(1) - константа вне зависимости от кол-ва поданных данных (здесь и далее "n") затраты по времени/по памяти не зависит от количества элементов.
2. O(log n) - логарифмическая, тут интересней и самое простое это, если читатель ознакомлен с понятием бинарного дерева, ибо иначе объяснять это чутка веселее) так что пока опустим
3. O(n) - линейная, о, самый простой кадр.
Пришло на вход n элементов? Необходимо проверить все из них или половину/треть, или иную часть? Это линейная сложность
4. O(n log n) см. Пункт 2
5. O(n^2) - квадратная сложность.
Это когда тебе нужно свершить над поданными тебе данными такое действие, что ты для каждого элемента должен ты перепроверить все остальные элементы твоего массива данных ( вот тут не очень хорошо объяснил), но вдруг хоть этим помогу.
Есть понятное дело также иные степенные сложности, всякие случаи с "а что тут вообще делает m?". В общем и целом - весело. Ну и прошу учесть, что я этот текст тут из своего эгоизма вытащил, так что, если я вдруг неправ, надеюсь меня поправят более шарящие люди.