ПРИМЕЧАНИЕ. Это не все, что нужно знать о Big O, но это всего лишь шаг к тому, чтобы нарисовать мысленную картину того, что такое Big O, самым простым способом, который я могу объяснить.

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

  • Что такое нотация Big O и почему нотация Big O
  • Сложность времени и пространства

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

Основная концепция говорит о времени, необходимом для выполнения конкретной задачи с заданными входными данными.

Почему используется обозначение Big O —

В компьютерных науках нотация большого O используется для классификации алгоритмов в зависимости от того, как растут их требования к времени выполнения или пространству по мере увеличения размера входных данных. Другими словами, он измеряет временную или пространственную сложность функции. Это означает, что мы можем заранее знать, насколько хорошо алгоритм будет работать в конкретной ситуации. — Николас Оберт

Давайте поговорим о порядке роста в Big O относительно временной сложности.

O(1) — постоянное время

Говорят, что O (1) находится в постоянном времени, потому что шаги не масштабируются при передаче входных данных в функцию.

// EXAMPLE OF A CONSTANT FUNCTION - BIG O(1)
function constant(arr) {
  let result = 100 * 1000; // constant function - Big 0(1)
  return result; // constant function - Big 0(1)
  // it is constant because the input does not affect the operation   being perform
}
let arr = [1,2,3,4,5];
console.log(constant(arr))
--- Output ---
100000

В приведенном выше примере мы видим, что ввод arr, который передается функции, не влияет на операцию, выполняемую функцией, а это означает, что каждый раз, когда эта функция вызывается, результат всегда будет постоянным.

0(n) — линейное время

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

// EXAMPLE OF A LINEAR FUNCTION - BIG O(n)
function linear(arr) {
  for (let n= 0; n < arr.length; n++) {
     // linear function - Big 0(n)
     console.log(arr); // constant function - Big 0(1)
     let result = 100 * 1000; // constant function - Big 0(1)
     console.log(result); // constant function - Big 0(1)
  }
}
let arr = [1,2,3,4,5];
console.log(linear(arr))
--- Output ---
100000

В приведенном выше примере мы видим, что цикл for является линейной функцией, поскольку N равно количеству задач, которые необходимо выполнить. При рассмотрении эффективности функции.

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

Логарифм – это степень, в которую нужно возвести число, чтобы получить другое число. Log2 по основанию 8 = ²³ = 2x2x2 = 8.

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

// -- EXAMPLE OF LOGARITHMIC FUNCTION  - BIG O(log n) --
// This is a recursive function because it calls itself
function logFuncA(n) {
   if (n === 0) return "Done"; // constant function - Big 0(1)
   n = Math.floor(n / 2); // linear function - Big 0(n)
   return logFuncA(n);
}
// This is a iterative or non-recursive function
function logFuncB(n) {
  while (n > 1) {
  n = Math.floor(n / 2); // linear function - Big 0(n)
  }
 
  return n;
}

В приведенном выше примере logFuncA у нас есть рекурсивный алгоритм, который

O (n log n) — линейное арифмическое время

Линейно-арифмическое время O(n log n) — это Muddy Mudskipper временных сложностей — худшее из лучших (хотя и менее седое и двуличное). Это умеренная сложность, которая плавает вокруг линейного времени O (n), пока входные данные не достигнут расширенного размера, занимая время, пропорциональное O (n log n), для обработки входных данных размера n.

// -- EXAMPLE OF LOGARIMTIMC FUNCTION  - BIG O(n log n) --
function nLogNFunc(n) {
  let y = n; // constant which is Big O(1)
  while (n > 1) {
      // complexity of Big O(log n)
      n = Math.floor(n / 2);
     for (let i = 1; i <= y; i++) {
       // linear complexity Big O(n)
       console.log(i);
     }
  }
}
let n = 8;
console.log(nLogNFunc(n))

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

O (n²) алгоритм, производительность которого прямо пропорциональна квадрату размера набора входных данных, что в основном приводит к квадратной матрице с одинаковым количеством строк и столбцов.

// EXAMPLE OF A QUADRATIC FUNCTION - BIG O(n2)
function quadratic(n) {
     // quadratic function - Big 0(n2)
     for (let i = 0; i < n.length; i++) {
           // linear function - Big 0(n)
        for (let j = 0; j < n.length; j++) {
            // linear function - Big 0(n)
           console.log(i, j); // constant function - Big 0(1)
        }
    }
}
let n = 4;
console.log(quadratic(n))
--- Output ---
16

В приведенном выше примере у нас есть два цикла for (i, j), где j вложен в i, алгоритм будет проходить i nчислораз, чтобы получить j .

when i = 0, j = 0
     i = 0, j = 1
     i = 0, j = 2
     i = 0, j = 3 
...
4 x 4 = 16
4^2   = 16

O(n³) — кубическое время

В случае кубической сложности время обработки алгоритма пропорционально кубу входных элементов. Сложность следующего алгоритма 10*10*10 = 1000. Три петли имеют максимум 10. — Источник

O(n³) такой же, как O(n³), но с дополнительным шагом, он занимает O(n) на 3-м месте, в другом случае, чтобы заставить алгоритм работать.

// EXAMPLE OF A CUBIC FUNCTION - BIG O(n3)
function cube(n) {
// cubic function - Big 0(n3)
   for (let i = 0; i < n.length; i++) {
       // quadratic function - Big 0(n2)
      for (let j = 0; j < n.length; j++) {
        // linear function - Big 0(n)
          for (let k = 0; k < n.length; k++) {
              console.log(i, j, k); // constant function - Big 0(1)
          }
       }
    }
}

O(2n) — Фибоначчи или экспоненциальное время

Алгоритм с экспоненциальным временем — это алгоритм, время выполнения которого растет как экспоненциальная функция размера его входных данных.

Последовательность Фибоначчи — это набор целых чисел (числа Фибоначчи), который начинается с нуля, за которым следует единица, затем еще одна, а затем ряд постоянно возрастающих чисел. Последовательность следует правилу, согласно которому каждое число равно сумме двух предыдущих чисел. - "Источник"

Например: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34.

// -- EXAMPLE OF FIBONACCI SEQUENCE --
function fib(n) {
  if (n === 0) {
    return 0;
  }
  if (n === 1) {
    return 1;
  }
  return fib(n - 1) + fib(n - 2);
}

Пусть n обозначает длину входных данных алгоритма.

O(n!) — факториальное время.

O (n!) Этот алгоритм принимает входные данные и умножает каждое число до входного числа в другом, чтобы получить результат.

For example: 5! = 5 * 4 * 3 * 2 * 1 = 120

// -- EXAMPLE OF FACTORIAL FUNCTION --
function f() {
    if (n === 0) {
        console.log("*************");
      return;
    }
    for (let i = 0; i < n; i++) {
     return f(n - 1);
    }
}

Приложение

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

P.S. — Пожалуйста, убедитесь, что вы следите.