Большая нотация “О

Нотация Big O – это способ описания того, как временная сложность/эффективность алгоритма зависит от размера данных, которые он обрабатывает.

Привет и добро пожаловать на курс. Сейчас мы немного сменим тему. Мы хотим поговорить о том, что называется временной сложностью, или временной эффективностью, а также о вращении Big O. Нотация Big O – это просто нотация, которую вы используете для описания временной сложности алгоритма на структуре данных. И если бы вы изучали курс информатики или получали степень по информатике, это была бы большая тема, и вы бы обсуждали различные алгоритмы и различные структуры данных в более общем смысле, то есть вы бы не просто сосредоточились на Python. Вы также будете говорить о структурах данных, которые, возможно, реализованы в других языках иначе, чем в Python.

Таким образом, это будет скорее высокоуровневое обсуждение различных алгоритмов и структур данных. И это замечательно. Это очень хорошо. Но в этом курсе мы немного больше сосредоточены на Python. Поэтому мы познакомимся с идеей нотации Big O на нескольких примерах. А затем мы очень быстро перейдем к Python, чтобы обсудить временную сложность конкретных структур данных Python, таких как список, сайт или словарь. Итак, первое, что мы хотим сделать, это поговорить о нотации Big O. Что это такое? И почему нас это волнует?

Чтобы представить ее, давайте рассмотрим два примера. Это просто воображаемые примеры. В первом примере я даю вам словарь, в котором тысяча слов. Но слова расположены не в алфавитном порядке. Фактически, они случайны. И затем я прошу вас найти в словаре определение того или иного слова. И как вы должны будете это сделать? Вы не знаете, где это слово находится в словаре. Он не алфавитный. Он совершенно случайный. Поэтому вам придется начать с первого слова и перебирать все слова, пока вы не найдете это слово, и тогда вы сможете дать мне определение.

Или вы просмотрите весь словарь и скажете мне, что этого слова нет в словаре. Итак, если словарь состоит из 1000 слов, то вам потребуется 1000 шагов, верно? Вы должны посмотреть на каждое слово и понять, есть ли это слово или нет. Если бы я дал вам словарь на миллион слов, это заняло бы миллион шагов. В худшем случае, это займет миллион шагов. То есть в худшем случае слово, которое вы ищете, будет самым последним в словаре, или его там вообще не будет, и в этом случае вы все равно переберете все слова.

И часто, когда мы говорим о временной сложности алгоритмов, мы часто говорим о наихудшем случае. Итак, в данном примере алгоритм состоит в том, что вы просто просматриваете каждое слово в словаре. А если бы это был словарь на миллион слов, то потребовался бы миллион шагов, или в худшем случае

И на этот раз он упорядочен по алфавиту. А еще у него есть красивые вкладки по бокам. Так что вы можете очень быстро перейти к нужному разделу. На самом деле, вкладки включают две буквы. То есть, в нем есть вкладки AA, AB, AC. Так что если первые две буквы слова начинаются с AA, вы сможете почти сразу перейти к нему. И еще мы скажем, что вы очень хорошо умеете определять, на какую страницу вам нужно перейти. Поэтому вы используете вкладки. И если она находится посередине между двумя вкладками, вы очень хорошо умеете переходить прямо к середине. ХОРОШО. Теперь я попрошу вас найти слово.

И сколько шагов у вас на это уйдет? Ну, это займет около одного шага, потому что вы можете сразу перейти к слову. Это очень просто. Вам не нужно перебирать каждое слово. Я прошу вас найти зебру. И вы переходите на вкладку ZE. Вы переходите прямо к ней. И теперь, если я дам вам слово с миллионом – или, простите, дам вам словарь с миллионом слов в нем, это все равно займет у вас всего один шаг. Если я дам вам словарь с десятью миллионами слов, это все равно будет один шаг, потому что в нем есть все вкладки, и вы действительно хорошо умеете переходить на нужную страницу.

Так что между этими двумя примерами огромная разница, верно? Один ужасно медленный. И не только это, но и масштабирование. Количество шагов, которые вам нужно сделать, увеличивается по мере роста количества слов в словаре, верно? Во втором примере, он не масштабируется. Вы можете дать мне словарь на 100 миллионов слов, и это все равно будет примерно один шаг. Теперь, я знаю, что в реальной жизни, верно, вы перелистываете страницу туда, где, по вашему мнению, она находится, а затем вам, вероятно, придется перелистнуть пару страниц влево или вправо. Но все равно, по сути, это одинаковое количество времени, независимо от того, насколько велик словарь. И эту разницу мы и хотим описать. Потому что это огромная разница.

Итак, нотация Big O – я собираюсь выделить некоторый текст здесь внизу – как вы пишете нотацию Big O? Сначала я расскажу вам, как ее писать. А потом я расскажу, почему мы пишем ее именно так. Я думаю, это будет иметь немного больше смысла. Но сначала мы просто перейдем к тому, как писать большую О, что это такое. Ну, вы пишете заглавную О, и эта О – сокращение от order. А затем вы пишете в скобках порядок n, с которым масштабируется алгоритм, где n – это размер данных, на которых вы запускаете алгоритм.

Так что в нашем первом примере, на самом деле, прежде чем я скажу это, когда я говорю порядок n, это означает, что существует некоторая нелинейная функция n, которая описывает, как алгоритм, как шаги в алгоритме масштабируются с n. Я знаю, что это может звучать запутанно. Но давайте рассмотрим мощность n. Итак, мощность n нелинейна. Это нелинейная функция, мощность n. Поэтому давайте просто пройдемся по некоторым мощностям n прямо здесь. Итак, у нас есть n, возведенное в нулевую степень, которая равна единице. Таким образом, любое число, возведенное в нулевую степень, равно единице. У нас есть n, возведенное в первую степень, которое просто n, верно? N в первой степени – это N.

Любое число, возведенное в первую степень, равно n. Число, возведенное во вторую степень, равно n в квадрате. N третьей степени – это n в кубе, и так далее, и так далее. Итак, если бы мы собирались описать эти два примера в виде степени n, как бы мы их описали? И это действительно просто. Может быть, говорить о силе и не совсем понятно, но эти примеры действительно просты. Пример один, мы уже говорили, что он занимает столько же шагов, сколько слов в словаре. Так что если в словаре n слов, это займет у вас n шагов. И опять же, в худшем случае, когда нам придется перебирать каждое слово.

Поэтому мощность n, с которой он масштабируется, или я должен сказать, что порядок n, с которым он масштабируется, равен n, или n до первой мощности. Так что если бы мы собирались написать нотацию Big O, то это было бы просто Big O, а затем в скобках – n. Таким образом, порядок n, с которым он масштабируется, это просто n. Это не n в квадрате. Это не n в кубе, верно? Это не что-то еще. Это просто n. Теперь, второй пример – один шаг, независимо от того, насколько велик словарь. Так что это просто один шаг. Поэтому вы пишете O от 1. А один – это то же самое, что n нулевой степени, верно?

Если бы вы хотели быть более сложными, вы могли бы написать O от n, возведенного в нулевую степень. И это означает, что независимо от того, насколько большим становится m, вы просто увеличиваете его до нулевой степени, и получается единица. Таким образом, оно вообще не масштабируется с n. Это постоянное время. Другой способ сказать, что Big O – это просто постоянное время. Алгоритм занимает одинаковое количество времени независимо от того, насколько велики данные.

Итак, это было быстрое и грязное введение в нотацию Big O. Есть и другие. На самом деле, мы увидим это в одной из следующих лекций. Мы увидим другие виды общих порядков. Но O один, порядок один является общим. И O n – общий. И O n в квадрате также является общим. Так что теперь, в ближайших лекциях, мы рассмотрим еще несколько примеров, чтобы нам было действительно удобно пользоваться нотацией Big O.

Поделиться этим постом

Нотация Big O – это способ описать, как временная сложность/эффективность алгоритма (или функции) зависит от размера данных, которые он обрабатывает.

В этом видео вы познакомитесь с идеей нотации Big O, а также пройдете несколько примеров, поясняющих это.

Продолжение

Файл, используемый в этом видео, – Introducing Time Efficiency and Big O Notation.ipynb . Пожалуйста, скачайте этот файл в разделе “Загрузки” ниже.

Присоединяйтесь к обсуждению

В начале этого видео был задан вопрос: Что такое нотация Big O, и почему она должна нас волновать? После просмотра этого видео, какие у вас мысли по этому поводу?

Воспользуйтесь разделом “Комментарии” ниже и сообщите нам о своих мыслях. Постарайтесь ответить хотя бы на одно другое сообщение, и как только вы будете довольны своим вкладом, нажмите кнопку Отметить как выполненный, чтобы отметить этот шаг, после чего вы сможете перейти к следующему шагу.