Алгоритмы. Начало

Про важность алгоримтов говорить бессмысленно: мы можем как угодно ускорять компьютеры, но плохо и не оптимально написанный код на супер мощном компьютере — это плохо и не оптимально написанный код на супер мощном компьютере☺ История уже знала миллион случаев, когда оптимальное решение на небольшом, уютном тостере делало аналогичное, но плохо написанное решение на супер мощностях.

Итак, как же замерять алгоритм?

Алгоритм, а вернее его эффективность, обычно замеряется 2мя параметрами: затратами времени и памяти. Частенько встречаются алгоритмы, которые позволяют быстро решить задачу, но при этом требуют огромного количества памяти. В моих постах, я буду гораздо больше уделять времени оценке временных затрат, ну и конечно же немного поговорим о памяти.

Поговорим про оценку эффективности алгоритма ( тут и далее, оценка эффективности алгоритма — это временная оценка ) . Казалось бы, что сложного в замере времени выполнения алгоритма? Померил и круто. Минус, или радость, в том, что мы живем в недетерминированном мире, и если взять самый простой пример сортировки массива, у нас может быть практически бесконечное количство состояний этого массива.

Например, для того чтоб отсортировать массив такого вида: [0,1,2,3,4,5,6,7,8,9] и массив [2,4,3,5,8,7,6,9,0,1] потребуется различное количество времени. Ну и совсем много ( относительно ) потребуется времени для сортировки массива типа (9,8,7,6,5,4,3,2,1,0). Что самое интересное: для оценки алгоритма, нас мало интересует как алгоритм работает в идеальном случае, а нас интересует как же алогитм ведет себя в самой плохой для нас ситуации. Опять же, нас не интересует сколько имени времени затрачивается на алгоритм, и вот почему:

1. Один алогритм требует 3n + 5 шагов для выполнения
2. Второй алгоритм требует 2 * n^2 шагов

Какой из этих алгоримов лучше? Пока n = 0, 1, 2 выигрывает второй алгоритм. Но как только алгоритм переваливает за 2 — второй начинает проигрывать. Потому нас больше интересует с какой скоростью растут временные затраты на тот или иной алгоритм.

И опять же если у нас есть три алгоритма:

1. 2 * n ^ 2
2. n ^ 2
3. n ^ 3

Однозначно второй алгоритм лучше первого ( хотя бы в два раза ), но намного лучше третьего, потому как он в любом случае при увеличении n — растет намного быстрее.

Такой показатель называется Big O notation, и для его выведения есть ряд правил, которые помогают нам определить эффективность алгоритма без лишней мишуры:

1. Постоянные множители можно опускать. Например, для опеределения сложности алгоритма, 14 * n ^ 2 это тоже самое что и n ^ 2
2. n ^ a растет быстрее чем n ^ b, если a > b. Тоесть если сложность нашего алгоритма n ^ 2 + n — сложность для нас будет n ^ 2
3. Экспонента растет быстрее многочлена. 3 ^ n > n ^ 3
4. Полином растет быстрее логарифма. n^2 > n log(n)

График роста сложности алгоримтов

Дальше будет☺