Примеры

Константное время - constant time - O(1)

function constantTime(n) {
  for (let i = 0; i < 10; i++) {
    n += i;
  }
  console.log(n);
}

Линейное время - linear time - O(n)

function linearTime(n) {
  for (let i = 1; i <= n; i++) {
    console.log(i);
  }
}

Время пропорциональное квадратному корню - square root time - O(√n)

function squareNTime(n) {
  // пример ниже для n = 16
  for (let i = 1; i * i <= n; i++) {
    console.log(i * i);
  }
}

Единая неделимая операция процессора

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

function operation(n) {
  let a = 1;

  for (let i = 0; i < n; i++) {
    // do something
  }

  a++;
  // да, мы понимаем что operation(5) быстрее operation(100),
  // но это не имеет отношения к оценке сложности
}

Несколько циклов линейной сложности = линейной сложности

function linearAgain(n) {
  let a = 1;

  for (let i = 0; i < n; i++) {
    // do something
  }

  for (let i = 0; i < n; i++) {
    // do something
  }

  a++;
}

Переменная a и её инкремент
Инициализация переменной a - это операция инициализации, которая выполняется один раз. Сложность O(1).
Операция инкремента a++ также выполняется один раз. Сложность O(1).

Первый цикл
Цикл, который выполняется n раз. Сложность O(n).

Второй цикл
Второй цикл, который также выполняется n раз. Сложность O(n).

Суммарная сложность

• Инициализация переменной и её инкремент: O(1) + O(1) = O(2) = O(1).
• Первый цикл: O(n).
• Второй цикл: O(n).

Общая сложность: O(1) + O(n) + O(n) + O(1).
При сложении этих сложностей мы получаем:
O(1) + O(n) + O(n) + O(1) = O(2) + O(2n) = O(2 + 2n)

В асимптотическом анализе мы игнорируем константы, поэтому сложность сводится к O(n).

Таким образом, сложность функции linearAgain составляет O(n), так как доминирующим фактором является количество итераций циклов, которые выполняются n раз.

Сложность O(n + k)

function twoParametersOne(n, k) {
  let a = 1;

  for (let i = 0; i < n; i++) {
    a += i;
  }

  for (let i = 0; i < k; i++) {
    // do something
  }

  a += k;
  a++;
}

Сложность O(n * k)

function twoParametersTwo(n, k) {
  let a = 0;

  for (let i = 0; i < n; i++) {
    for (let j = 0; j < k; j++) {
      console.log(a++);
    }
  }

  return a;
}

Анализ функции twoParametersTwo

Функция twoParametersTwo имеет два вложенных цикла:

• Внешний цикл выполняется n раз.
• Внутренний цикл выполняется k раз для каждой итерации внешнего цикла.

На каждой итерации внутреннего цикла значение a увеличивается на 1.

При n = 5 и k = 3

1. Итерация внешнего цикла (i = 0)

   • Внутренний цикл выполняется 3 раза
     • a = 0 -> a = 1
     • a = 1 -> a = 2
     • a = 2 -> a = 3

2. Итерация внешнего цикла (i = 1)

   • Внутренний цикл выполняется 3 раза
     • a = 3 -> a = 4
     • a = 4 -> a = 5
     • a = 5 -> a = 6

3. Итерация внешнего цикла (i = 2)

   • Внутренний цикл выполняется 3 раза
     • a = 6 -> a = 7
     • a = 7 -> a = 8
     • a = 8 -> a = 9

4. Итерация внешнего цикла (i = 3)

   • Внутренний цикл выполняется 3 раза
     • a = 9 -> a = 10
     • a = 10 -> a = 11
     • a = 11 -> a = 12

5. Итерация внешнего цикла (i = 4)

   • Внутренний цикл выполняется 3 раза
     • a = 12 -> a = 13
     • a = 13 -> a = 14
     • a = 14 -> a = 15

Таким образом, при n = 5 и k = 3, значение a в конце выполнения функции будет равно 15.

Квадратичное время - quadratic time - O(n^2)

function nSquareTime(n) {
  for (let i = 1; i <= n; i++) {
    for (let j = 1; j <= n; j++) {
      console.log("hello world!");
    }
  }
}

Логарифмическое время - logarithmic time - O(log n)

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

Основы

Логарифм — это математическая функция, обратная возведению в степень. В контексте логарифмического поиска наиболее часто используется логарифм по основанию 2, который отвечает на вопрос: "Сколько раз нужно умножить 2 на само себя, чтобы получить данное число?" Например, логарифм числа 8 по основанию 2 равен 3, потому что 2 в степени 3 = 8.

Бинарный поиск подробно будет обсуждаться в лекции 3 - Алгоритмы поиска и сортировки.