Как долго что-то запускается? Это масштабируемо? Удобочитаемый? Big O измеряет время выполнения данного кода. Как повышается эффективность программы по мере увеличения данных? Big O звучит как куча дерьма, не так ли? Тем не менее, это помогает при изучении того, как память, пространство и данные работают в заданном алгоритме. Это то, что я узнал до сих пор.

Большой O — n — это просто стандартное соглашение, означающее, что оно зависит от количества заданных входных данных. Он вычисляет эффективность данного алгоритма.

O(n) или линейное время является наиболее распространенным, что соответствует диаграмме сложности. По мере того, как вещи становятся все больше и больше, масштабируется ли это? Хорошо, учитывая количество заданных элементов, оно масштабируется относительно количества (n) элементов, заданных в данной функции.

O(1) или постоянное время. Независимо от того, сколько элементов добавлено в данную коллекцию, для выполнения данной функции потребуется одинаковое количество операций. Например…. захват первого элемента в массиве. Массив может быть 15, 1070960 или 123906210, но для захвата первого элемента в этом массиве все равно потребуется одна операция. Входными данными могут быть данные любого типа, а не только массивы. Предсказуемость это хорошо.

O(n^2) или квадратичное время. Это означает, что каждый раз количество элементов увеличивается квадратично. Он увеличивается довольно быстро, что ужасно (довольно медленно), когда дело доходит до масштаба.

O(n!) или Факториал — самый дорогой и крутой из всех. Вы не столкнетесь с этим, так как это так плохо. Это похоже на добавление вложенного цикла для каждого входа.

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

При расчете Big O мы всегда думаем о наихудшем случае, когда дело доходит до масштабирования ваших входных данных. Обычно это зависит от скорости и доступной памяти (ОЗУ). Есть шпаргалка, которая может помочь, когда дело доходит до подготовки к интервью, которую мне дали. Я вам тоже все передам!

Шпаргалка по Big O: -Big O’s

O(1) Константа — без циклов

O(log N) Логарифмический — обычно алгоритмы поиска имеют log n, если они отсортированы (двоичный поиск).

O(n) Линейный — циклы for, while перебирает n элементов

O(n log(n)) Log Linear — обычно операции сортировки

O(n²) Квадратичный: каждый элемент в коллекции необходимо сравнивать с любым другим элементом. Два вложенных цикла

O(2^n) Экспоненциально-рекурсивный алгоритм, решающий задачу размера N

O(n!) Факториал: вы добавляете цикл для каждого элемента

Повторение половины коллекции по-прежнему составляет O(n) Две отдельные коллекции: O(a * b)

  • Что может вызвать время в функции?
  • Операции (+, -, *, /)
  • Сравнения (, ==)
  • Зацикливание (для, пока)
  • Внешний вызов функции (функция())

Книга правил

  • Правило 1. Всегда наихудший случай
  • Правило 2. Удаляйте константы
  • Правило 3. У разных входных данных должны быть разные переменные. О(а+б). Вложенные массивы A и B будут O(a*b) + для шагов по порядку * для вложенных шагов
  • Правило 4: Отбрасывайте неосновные термины - Что вызывает сложность пространства? - Переменные Структуры данных Выделение вызовов функций