Правила большого О
3. Различные термины для входных данных
Это может показаться вам сложным, но потерпите меня здесь.
Давайте рассмотрим пример.
У меня есть точно такая же функция, которую мы видели на прошлом уроке, которая дважды сжимает блоки. Я использую синтаксис for each в javascript для двойного цикла по одному и тому же массиву.
Мы уже знаем, что большой O для этой функции равен O(2n) или O(n), если мы отбросим константы.
Теперь третье правило гласит, что разные термины для входных данных. Поэтому, если мы изменили входные данные нашей функции:
Здесь у нас есть boxes и boxes2 в качестве первого и второго параметров. Если наш второй цикл for проходит через boxes2, как вы думаете, что здесь за большой O?
У вас может возникнуть соблазн подумать, что это O(2n) или O(n), если мы отбросил константы, но боюсь, вы ошибетесь.
Если это различные термины для входных данных, что в данном случае наши входные данные действительно разные — коробки могут иметь длину 100 элементов, а коробки2 могут иметь только 1 элемент, то результаты первого цикла for зависят от того, насколько велики первые входные данные, а результаты второго цикла for будут зависеть от того, насколько велик второй параметр. является.
Имейте в виду, что n — это просто произвольная буква, которую мы выбрали. Вместо этого мы могли бы сказать, что большой O этой функции что-то вроде O(a + b), или O(boxes1 + boxes2).
Вывод, таким образом, состоит в том, что если вы видите два цикла for один за другим, это не значит, что они повторяют одни и те же элементы.
Вложенные циклы
Предположим, вам нужно найти все возможные пары массива с номерами [1, 2, 3, 4, 5]. Это означает, что вам придется записывать 1–2, 1–3, 1–4, 1–5, затем 2–1, 2–2, 2–3,….
Здесь наша первая итерация с i захватит числа 1, 2, …. Но затем мы хотим перебрать числаснова с помощью jи записать 1–1, 1–2, 1–3, 1–4,1–5. Давайте запустим эту функцию и посмотрим, что произойдет.
Здесь вместо двух циклов for —один за другим, где мы используем сложение, с двумя вложенными циклами for это умножение; О (n²).
Если мы представим эту функцию на графике, мы увидим, что каждый раз, когда количество элементов увеличивается, мы видим, что наша функция увеличивается квадратично. Это называется квадратичным временем.
Если мы вернемся к графику с большим O, мы увидим, что o(n²) ужасно.
Многие алгоритмические проблемы включают преобразование алгоритма, который изначально был O(n²), в нечто более быстрое — возможно, в O(n log n), O(n)...
Если мы вернемся к правилу номер три, которое мы обсуждали — разные термины для входных данных, и посмотрим на наш пример:
Если бы эти циклы были вложенными, то вместо O(a + b) мы получили бы O(a * b).
И это правило номер три. Мы убеждаемся, что если у нас есть разные массивы, нотация большого O отличается, потому что мы не знаем их длины.
Простое практическое правило:
Для одинакового отступа — то есть, если массивы расположены друг за другом — вы добавляете; для отступа, который является вложенным — вы умножаете.
