Cout<<"Big O";

Как вы думаете, какая вещь невероятна огромна? Конечно же сложность алгоритмов, которые пишут новички. Что такое сложность алгоритмов, и причем тут буква "О"(большая), давайте разбираться.

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

1. Константа. О(const) - самые эффективные алгоритмы. Действия происходят моментально. Примером является обращение к элементу массива (mas[5]). Сложность - О(1).
2. Линейный алгоритм - О(n). Если вам удалось решить сложную задачу за О(n) - вы победили задачу. Очевидно, что при сложности O(n) совершается n операций. Пример - обход всех чисел массива. Алгоритмы О(n) невероятно эффективны, можно считать работают практически мгновенно.
3. Логарифмическое время - О(log2(n)) - как вы знаете, цифра "2" в программирования магическая, ведь все основано на двух состояниях "лампочек" - вкл/выкл. Алгоритмы О(log2(n)) также невероятно эффективны. Примером такого алгоритма является бинарный поиск.
4. Зачастую многие отличные алгоритмы, предназначенные для решения не самых простых задач работают за О(nlog2(n)). Это в разы медленней, чем 2 и 3 пункты по отдельности, но в разы быстрее, чем алгоритмы описанные ниже.
5. Плохой алгоритмы - степень. n^2, n^3 - иногда приемлемо, но дальше - нет(вернее, такие алгоритмы существуют, в некоторых задачах им альтернатив еще не создали, но подобные алгоритмы уже считаются на суперкомпьютерах - огромные затраты времени). Примером классического алгоритма О(n^2) является цикл, вложенный в другой цикл.
6. Ужасно - факториал - О(n!). Говорят, что факториал 80 равняется количеству песчинок на Земле. Думаю, с ним все понятно).

Также хочется отметить, что если код содержит несколько различных алгоритмов, то в большинстве случаев алгоритм с меньшим О не учитывается. Например алгоритм включает в себя три вложенных цикла от 0 до n, и отдельно от них один такой же цикл. Получаем О(n^3) + O(n), где второе настолько мало по сравнению с О(n^3), что О(n) не учитывается.

С ув. TechMentor.