Когда вы ищете Big O в Google, это первый результат, который появляется:

У меня есть поправка к этому определению: нотация Big O не является предметом бесчисленных девчачьих разговоров, но я бы хотел, чтобы это было так. Это действительно пригодилось бы, когда я пытался узнать о нотации Big O. Не говоря уже о том, что подумайте о том, сколько женщин уже много знают о нотации Big O и могут хорошо разбираться в этой теме, когда она поднимается на работе, во время интервью или на сетевых мероприятиях. Я знаю, супер сексуально.

Поговорим о нотации Big O!

Что это?

Нотация Big O - это общий язык, который мы используем, чтобы говорить о том, как быстро время выполнения алгоритма растет по сравнению с вводом. Это очень интересный способ сказать кому-то что-то вроде: «Ваш алгоритм будет хорошо масштабироваться по мере роста входных данных и все еще будет иметь довольно быстрое время выполнения, сладко» или «Ваш алгоритм не будет хорошо масштабироваться, если ваши входные данные будут расти, облом». , вам следует изменить его, чтобы масштабировать лучше ».

Цель Big O - измерить , насколько быстро увеличивается время выполнения по сравнению с вводом. Поскольку мы измеряем это, а не точное время выполнения одного алгоритма в частности, мы не можем измерить это время, и нам нужно измерить это с помощью чего-то другого. Вот тут-то и пригодится нотация Big O!

В нотации Big O мы используем n для обозначения размера ввода (во всяком случае, для первого ввода, подробнее об этом позже). Это сделано для того, чтобы мы могли сказать что-то вроде «время выполнения увеличивается в соответствии с размером входных данных» с такими обозначениями: O (n). Мы также можем сказать что-то вроде «время выполнения увеличивается пропорционально квадрату размера входных данных» с такими обозначениями: O (n ²).

Это супер абстрактно. Давайте рассмотрим несколько примеров!

Некоторые примеры

Мне нравится ссылаться на эту диаграмму, когда я пытаюсь разобраться в различных сложностях Big-O. Все следующие примеры написаны на Ruby.

  1. O (1) - постоянное время
def puts_first_item(items)
  puts items[0]
end

Время выполнения этой функции увеличивается в размере одного или постоянного времени. Массив items может иметь значение 1 или 1000, а временная сложность печати первого элемента массива останется постоянной. Это лучший сценарий для временной сложности.

2. O (log n) - логарифмическое время.

def binary_search(any_array, item)    
  first = 0    
  last = any_array.length - 1     
  while first <= last        
    i = (first + last)/2         
    if any_array[i] == item            
      return "#{item} found in array at position #{i}"       
    elsif any_array[i] > item            
      last = i - 1        
    elsif any_array[i] < item            
      first = i + 1        
    else            
      return "#{item} not found in this array"        
    end    
  end
end

Наиболее распространенный пример, используемый для логарифмического времени, - это двоичный поиск, который я использовал здесь. Обратите внимание, что входной массив необходимо отсортировать перед поиском для двоичного поиска. В основном, как определить O (log n), если нам нужно перебирать все более уменьшенные версии n за одну операцию. Для этой функции: 10x данных означает 2x временную сложность. Это второй лучший вариант для временной сложности.

3. O (n) - линейное время

def puts_first_item(items)
  items.each do |item|
    puts item
  end
end

Для этой функции: 10x входные данные означают 10x временную сложность. Если в массиве 10 элементов, мы должны поместить item 10 раз. Если в массиве 1000 элементов, мы должны поместить item 1000 раз. Такой линейный.

4. O (n log n) - квазилинейное время

Хорошим примером этого является алгоритм quicksort. Квазилинейное время означает, что при десятикратном увеличении входных данных мы будем иметь 20-кратную временную сложность. Звучит не очень хорошо, но подождите. По мере продвижения становится хуже.

5. O (n²) - квадратичное время

def puts_two_items(items)
  items.each do |first_item|
    items.each do |second_item|
      puts first_item, second_item
    end
  end
end

Обратите внимание на двойной вложенный цикл и каждый цикл, использующий один и тот же входной массив n. Вот откуда мы знаем, что эта функция имеет временную сложность O (n²). Для этой функции: 10x входные данные означают 100x временную сложность. Йоуза.

6. O (2 ^ n) - субэкспоненциальное время

def fibonacci(n)
   n <= 1 ? n : fibonacci(n - 1) + fibonacci(n - 2) 
end
puts fibonacci(10)

Хорошим примером этого является что-то вроде рекурсивной функции Фибоначчи, которую я здесь включил. В этой функции: 10x входные данные означают 1024x временную сложность. Другими словами, временная сложность здесь очень плохая при масштабировании относительно ввода.

7. O (n!) - Факториальное время

def factorial_runtime(n) 
  n.times do |n|
    factorial_runtime(n-1)
  end
end

В этом случае n - целое число, а не массив. Такая временная сложность чертовски плоха для масштабирования. Для этой функции: 10x входные данные означают 3628800x временную сложность. Ой.

Интересный факт: это далеко не все возможные временные сложности! Мы могли бы рассмотреть их все, но, вероятно, этот пост займет больше времени от Medium. Это лишь некоторые из наиболее распространенных, обсуждаемых мною на профессиональном уровне.

Почему это имеет значение?

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

Это действительно самая важная причина для понимания нотации Big O как разработчика программного обеспечения. Big O дает вам и вашим коллегам общую основу для обсуждения влияния различных алгоритмов на производительность при принятии технических решений на работе. Без него было бы намного труднее принимать коллективные и осознанные решения относительно производительности при написании алгоритмов вместе с другими людьми.

Почему вы открыли этот пост с определения Big O в Google?

Потому что это весело.

P.S. Дайте мне знать, если я здесь что-то не так. Заранее спасибо! :)