Большой O: сколько шагов относительно N элементов?
Отрывок из «Руководства по структурам данных и алгоритмам здравого смысла», второе издание — Джей Венгроу
Big O достигает согласованности, сосредотачиваясь на количестве шагов, которые выполняет алгоритм, но определенным образом. Начнем с применения Big O к алгоритму линейного поиска.
В худшем случае линейный поиск займет столько шагов, сколько элементов в массиве. Как мы уже говорили ранее: для N элементов в массиве линейный поиск может занять до N шагов. Подходящий способ выразить это в нотации Big O:
O(N)
Некоторые произносят это как «Большой О N». Другие называют это «Орден N». Однако лично я предпочитаю «Oh of N».
Вот что означает обозначение. Он выражает ответ на то, что мы назовем «ключевым вопросом». Ключевой вопрос: если есть N элементов данных, сколько шагов будет выполнять алгоритм? Идите вперед и прочитайте это предложение еще раз. Затем нарисуйте его у себя на лбу, так как это определение большой нотации O, которое мы будем использовать в оставшейся части этой книги.
Ответ на ключевой вопрос заключен в круглые скобки нашего выражения «большое О». O(N) говорит, что ответ на ключевой вопрос заключается в том, что алгоритм будет выполнять N шагов.
Давайте быстро рассмотрим мыслительный процесс для выражения временной сложности с помощью нотации Big O, снова используя пример линейного поиска. Сначала зададим ключевой вопрос: если в массиве N элементов данных, сколько шагов займет линейный поиск? Поскольку ответ на этот вопрос заключается в том, что линейный поиск займет N шагов, мы выражаем это как O (N). Для справки, алгоритм с O(N) также известен как алгоритм с линейным временем.
Давайте сравним это с тем, как Big O выражает эффективность чтения из стандартного массива. Как вы узнали из главы 1 Почему важны структуры данных, чтение из массива занимает всего один шаг, независимо от размера массива. Чтобы выяснить, как выразить это в терминах большого O, мы собираемся снова задать ключевой вопрос: если есть N элементов данных, сколько шагов займет чтение из массива? Ответ заключается в том, что чтение занимает всего один шаг. Итак, мы выражаем это как O (1), что я произношу О из 1.
O(1) интересно, поскольку, хотя наш ключевой вопрос вращается вокруг N («Если есть N элементов данных, сколько шагов будет выполнять алгоритм?»), ответ не имеет ничего общего с N. И в этом, собственно, весь смысл. . То есть, сколько бы элементов ни было в массиве, чтение из массива всегда занимает один шаг.
И именно поэтому O(1) считается «самым быстрым» алгоритмом. Даже по мере увеличения данных алгоритм O(1) не выполняет никаких дополнительных шагов. Алгоритм всегда выполняет постоянное количество шагов, независимо от того, каково N. Фактически, алгоритм O (1) также можно назвать алгоритмом с постоянным временем.
Итак, где математика?
Как я упоминал ранее в этой книге, я применяю простой для понимания подход к теме Большого О. Это не единственный способ сделать это; если бы вы прошли традиционный курс обучения алгоритмам в колледже, вы, вероятно, познакомились бы с Big O с математической точки зрения. Большое О изначально было понятием из математики, и поэтому его часто описывают математическими терминами. Например, один из способов описания Big O состоит в том, что он описывает верхнюю границу скорости роста функции или что если функция g(x) растет не быстрее, чем функция f(x), то говорят, что g член O(f). В зависимости от вашего математического образования это либо имеет смысл, либо не очень помогает. Я написал эту книгу, чтобы вам не нужно было столько математики, чтобы понять концепцию.
Если вы хотите углубиться в математику, лежащую в основе Big O, ознакомьтесь с полным математическим объяснением книги Введение в алгоритмы Томаса Х. Кормена, Чарльза Э. Лейзерсона, Рональда Л. Ривеста и Клиффорда Штейна (MIT Press, 2009). Джастин Абрамс также дает довольно хорошее определение в своей статье: https://justin.abrah.ms/computer-science/understanding-big-o-formal-definition.html.
Надеемся, вам понравился этот отрывок. Вы можете продолжить чтение A Common Sense Guide to Data Structures and Algorithms, Second Edition прямо на Medium.
Или купите электронную книгу прямо с The Pragmatic Bookshelf. В рамках нашей Весенней распродажи 2023 года вы можете сэкономить 50 % на этой книге, используя код DATAFLOW2023 до полуночи по восточному времени 25 апреля 2023 года.
Чтобы получить печатную копию, посетите bookshop.org.
