Как научиться определять алгоритмическую сложность "на глазок"?

"На глазок" это не всегда возможно сделать. Тем более, что в некоторых случаях важна не только алгоритмическая сложность, но и количество занимаемой памяти, а также сложность в "плохом случае". Тем не менее, есть несколько приемов, но для их применения придется хотя бы поверхностно разобраться в работе алгоритма.

Первое, что нужно понять: из определения О-нотации следует, что O(n/2) или O(5*n)  это то же самое, что O(n), т.е. умножение на ненулевую константу следует убирать из-под О. Отсюда же следует, например, что O(log2(n)) = O(ln(n)).

Далее нужно понять, что если есть два вложенных алгоритма, и внутренний не влияет на внешний, их сложности перемножаются. Если внутренний влияет на внешний, оценить общую сложность так просто не всегда получится.

Рассмотрим пару алгоритмов, не использующих вложенность:

• Требуется найти конкретное число в неупорядоченном списке чисел, содержащем это число. Иногда оно будет находиться в самом начале, иногда в конце или в середине. В среднем, это потребует n/2 операций сравнения. Но O(n/2) = O(n) - сложность линейная.

• Добавление элемента в дерево поиска, содержащее n элементов. Дерево поиска имеет корень и две ветки. Корень содержит значение (например, число), левая ветка имеет значение меньше корня, а правая - больше. Дальше каждая ветка может раздваиваться на две ветки, и т.д. Если требуется определить, содержит ли дерево искомое значение, нужно посмотреть его в корне, и если его там нет, сделать выбор - продолжить искать в левой ветке, или в правой. И так далее - это удобно делать с помощью рекурсии. Главное, что здесь нужно понять - все ветки дерева, измеряя от корня, будут иметь примерно одинаковую длину (если не учитывать "плохие случаи"). На первом уровне будет один элемент, на втором два, на третьем 2^3, и т.д. Отсюда можно посчитать, что длина ветки (количество уровней) будет примерно равным log2(n). Значит, двигаясь по дереву от корня, придется произвести log2(n) сравнений - значит, сложность алгоритма O(log2(n)) = O(ln(n)) - логарифмическая.