Изучение структур данных и алгоритмов всегда начинается с большой нотации O. Так что же такое на самом деле Big O и почему это так важно?
Написать решение данной проблемы несложно, труднее всего написать масштабируемое решение, которое хорошо работает, когда размер входных данных увеличивается.
Именно в этом нам помогает Big O — оценить качество решения, измерив его масштабируемость. Большой O не говорит нам, сколько времени займет решение, вместо этого он дает нам представление о том, как увеличится количество операций при увеличении входных данных.
Давайте посмотрим на различные распространенные обозначения Big O —
- О(1) — Лучший.
- O(log n) — лучше.
- О(н) — Хорошо.
- O(n²) — Плохо.
Есть еще несколько таких, как O(n!), что ужасно, и мы редко сталкиваемся с ними, поэтому давайте не будем рассматривать их в этой статье.
O(1) — Постоянное время.
В приведенном ниже коде количество операций постоянно — это означает, что независимо от того, насколько велик ввод, код будет выполнять постоянное количество операций. Если массив содержит 5 элементов, код выполнится один раз, если размер массива увеличится до 50 000 элементов, код все равно выполнится ТОЛЬКО ОДИН РАЗ. Это пример O (1).
Здесь следует отметить, что если в приведенной выше функции есть, скажем, 3 операции вместо 1, большой O будет O (3). Это означает, что независимо от размера ввода код всегда выполняет 3 операции.
O(log n) — логарифмическое время.
Сложность O(log n) проявляется, когда мы используем решения типа «разделяй и властвуй». Бинарный поиск — отличный пример сложности O(log n).
В приведенном ниже коде бинарного поиска мы многократно делим пополам часть массива, которая может содержать искомый элемент, пока не сузим возможные местоположения до одного.
O(n) — Линейное время.
В приведенном ниже коде количество операций линейно — это означает, что операция будет увеличиваться линейно в соответствии с размером входных данных. Если массив содержит 5 элементов, цикл for в приведенном ниже коде будет выполняться 5 раз, а если размер массива увеличится до 50 000 элементов, цикл будет выполнен 50 000 раз.
O(n²) — квадратичное время.
В приведенном ниже коде количество операций квадратичное. Это означает, что операция будет квадратично увеличиваться в соответствии с размером входных данных. В коде две петли. Для каждого элемента входного массива будут выполняться два цикла for. Следовательно, если размер массива равен 2, всего операций будет 4, если размер массива равен 3, всего операций будет 9.
Надеюсь, статья оказалась для вас полезной, оставляйте свои вопросы/отзывы в комментариях, буду рад ответить. Если вам понравилась статья, вы можете подписаться на меня в Medium и подключиться в LinkedIn.
