В этом блоге я расскажу, как мы определяем, к какой категории относится алгоритм, в нотации Big O Notation. Если вы не знакомы с Big O, то можете прочитать один из моих предыдущих блогов здесь, в котором объясняется каждая категория Big O.
Мы знаем, что нотация Big O относится к временной сложности алгоритма или, другими словами, к тому, сколько шагов делает алгоритм, если имеется N элементов. Однако есть несколько вещей, которые мы должны знать о Big O, чтобы определить, к какой категории относится алгоритм.
Игнорирование констант ✋🏼
В мире нотации Big O некоторые алгоритмы описываются точно так же, но могут различаться по скорости. Например, мы можем предположить, что более быстрый алгоритм - O (log n), если другой - O (N), но это не всегда так.
Давайте посмотрим на два алгоритма сортировки, которые могут помочь описать это явление - пузырьковая сортировка и сортировка по выбору.
Пузырьковая сортировка проходит через массив чисел, а затем стремится поменять местами два последовательных числа, чтобы получить наименьшее число в левой части, пока массив чисел не будет отсортирован в порядке возрастания. Сортировка пузырьков - это аптроним, поскольку мы увидим, что наибольшее число «пузырится» вверху справа, каждый раз, когда мы выполняем проход. По сути, два числа сравниваются друг с другом, чтобы определить, какое из них больше, и два числа меняются местами, чтобы отсортировать их. Теперь, если мы хотим описать его эффективность, мы бы сказали, что это O (n²). Почему? Потому что с увеличением количества элементов количество шагов растет в геометрической прогрессии. Если бы у нас было 5 элементов, максимальное количество шагов, которое потребовалось бы для сортировки с использованием пузырьковой сортировки, составило бы 20 шагов (до 10 сравнений и до 10 свопов).
Сортировка по выбору проходит через массив чисел, отслеживая, какое число является наименьшим, и когда наименьшее число будет найдено, оно заменит это число на числа в крайнем левом углу и будет проходить через таким же образом непрерывно, пока не будет отсортировано. По сути, наименьшее число сравнивается с каждым значением на каждом проходе и меняет местами наименьшее число на его правильную позицию. Теперь, если мы хотим описать его эффективность, мы бы сказали, что это также O (n²). Если бы нам нужно было иметь дело с 5 элементами, максимальное количество шагов, которое потребовалось бы для сортировки с использованием сортировки по выбору, составило бы 14 шагов (с учетом 10 сравнений и 4 свопов). Хорошо ... подождите ... подождите ... сортировка выбора требует меньше шагов для завершения алгоритма, чем пузырьковая сортировка, но также считается O (n²) ?!
Здесь мы видим, что сортировка выбора занимает примерно половину шагов n², и поэтому мы можем предположить, что подходящим способом назвать этот алгоритм является O (n² / 2). Другими словами, для числа N элементов имеется около n² / 2 шагов. Мы можем увидеть это через эту таблицу:
Итак, почему мы не включаем «/ 2», говоря о временной сложности сортировки выбора? Это потому, что нотация Big O игнорирует константы, т. Е. Большой O никогда не включает в себя обычные числа, не являющиеся экспонентой. В случае сортировки по выбору мы удаляем «/ 2» и получаем O (n²).
Зная это, если бы у нас был алгоритм, выполняющий 2N шагов (N * 2 шага), мы бы описали эффективность этого алгоритма как O (n), потому что мы удаляем все обычные числа.
Общие категории 🔢
Нотация Big O касается только общих категорий скоростей алгоритмов. Лучший способ понять это - провести аналогию, поэтому давайте поговорим об автомобилях. Конечно, существует множество типов автомобилей, которые относятся к разным категориям, например: микро, хэтчбек, купе, спорт, супер и т. д.
Если бы мы сравнили два разных автомобиля, один из которых - микро, а другой - суперкар, может стать неуместным упоминание, какой из них быстрее. Поскольку эти автомобили находятся на противоположных концах спектра, нам действительно не нужно приводить длинный список спецификаций для каждой из них. С таким же успехом мы можем просто пройти один как самый медленный, а другой как самый быстрый, или микро и супер.
То же самое относится к эффективности алгоритмов. Если мы сравним алгоритм O (n) и алгоритм O (n²), они будут совершенно разными, так что на самом деле не имеет значения, является ли O (n ) - алгоритм O (2n) или O (n / 2).
Причина, по которой алгоритмы O (n) и O (n²) могут быть разделены на две отдельные категории, но O (n) и O (2n) или O (n / 2) будет меньше, потому что Big O заботится о долгосрочной траектории шагов алгоритма по мере увеличения данных. На графике алгоритм O (n) будет представлен прямой линией и O (2n) или O (n / 2) алгоритм также будет прямой линией вокруг O (n). Однако O (n²) рассказывает нам совершенно другую историю экспоненциального роста, особенно на графике.
Все типы нотации Big O - O (1), O (n), O (n²), O (log n) и т. Д. - это общие категории, которые имеют огромную заметную разницу. Если бы мы умножили или разделили количество шагов на обычное число, это не заставило бы их перейти в другую категорию.
Однако, когда два алгоритма подпадают под одну и ту же классификацию Big O, это не обязательно означает, что оба алгоритма имеют одинаковую скорость или количество шагов, сделанных для его выполнения. Когда два алгоритма попадают в одну категорию, требуется дальнейший анализ, чтобы определить, какой алгоритм работает быстрее.
Я надеюсь, что это даст больше разъяснений по нотации Big O и классификации эффективности. Прочтите книгу Джея Венгроуза «Руководство по структурам данных и алгоритмам с здравым смыслом» для более подробного объяснения!
