O-нотация light version

Материал из Algocode wiki
Версия от 15:35, 21 августа 2019; Андрей Гаркавый (обсуждение | вклад) (добавил что такое N в одну из задач)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

O-нотация для самых маленьких

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

Зачем это нужно

Казалось бы, что для оценки времени работы можно просто физически измерять время, которое программа работает на разных входных данных. Здесь есть достаточное количество минусов:

  • на разных компьютерах время работы будет разным;
  • чтобы измерить время, придется запустить сам алгоритм, но иногда приходится оценивать алгоритмы, требующие часы или даже дни работы;
  • время будет учитывать какие-то вспомогательные операции, которые на самом деле в текущей оценке не нужны

Зачастую основной задачей программиста становится оптимизировать алгоритм, выполнение которого займёт тысячи лет, до какого-нибудь адекватного времени работы. Поэтому хотелось бы уметь предсказывать, сколько времени займёт выполнение алгоритма ещё до того, как мы его запустим.

Что и как учитывать

Чаще всего мы будем считать, что за условную единицу времени выполняются следующие операции (тут приведены не все, но принцип здесь виден):

  • арифметические операции ($*$, $+$, $-$, $/$, битовые сдвиги);
  • сравнение чисел;
  • присваивание;

Мы можем попробовать точно оценить количество таких операций, которые выполняются в программе. Но в большинстве случаев такого подробного разбора всех действий не требуется. Если вы посчитаете, сколько операций сравнения происходит в разных квадратичных сортировках, то получите разные выражения, где главный член - это $N^2$, умноженное на некоторую константу. Хочется придумать способ упростить эти формулы так, чтобы:

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

O-нотация

Для этого придумали $O$-нотацию - асимптотическое время работы вместо точного (часто его ещё называют асимптотикой).

Пусть $f(N)$ - это какая-то функция. Говорят, что алгоритм работает за $O(f(N))$, если существует число $C$, такое что алгоритм работает не более чем за $C \cdot f(N)$ операций.

В таких обозначениях можно сказать, что

  • Сортировка пузырьком работает за $O(N^2)$
  • Сортировка выбором работает за $O(N^2)$
  • Сортировка вставками работает за $O(N^2)$
  • Сортировка подсчетом работает за $O(N + M)$

Это обозначение удобно тем, что оно короткое и понятное, а также оно не зависит от умножения на константу или прибавления константы. Если алгоритм работает за $O(N^2)$, то это может значить, что он работает за $N^2$, за $N^2 + 3$, за $\frac{N(N-1)}{2}$ или даже за $1000 \cdot N^2 + 1$ действие. Главное, что функция ведет себя как $N^2$, то есть при увеличении $N$ (в данном случае это длина массива) он увеличивается как некоторая квадратичная функция. Например, если увеличить $N$ в $10$ раз, время работы программы увеличится приблизительно в $100$ раз.

Поэтому все эти рассуждения про то, сколько операций в `swap` или считать ли отдельно присваивания, сравнения и циклы - отпадают. Как бы вы ни ответили на эти вопросы, они меняют ответ на константу, а значит асимптотическое время работы алгоритма никак не меняется.

Задания

  1. Найдите асимптотику данных функций. Максимально упростите ответ (например, до $O(N)$, $O(N^2)$ и т. д.).
    • $\frac{N}{3}$
    • $\frac{N(N-1)(N-2)}{6}$
    • $1 + 2 + 3 + \ldots + N$
    • $1^2 + 2^2 + 3^2 + \ldots + N^2$
    • $\log{N} + 3$
    • $7$
    • $10^{100}$
  2. Найдите асимптотическое время работы данных функций:
    • int f(int n) {
          int s = 0;
          for (int i = 0; i < n; i++) {
              for (int j = 0; j < n; j++) {
                  s += i * j;
              }
          }
          return s;
      }
      
    • int g(int n) {
          int s = 0;
          for (int i = 0; i < n; i++) {
              s += i;
          }
          for (int i = 0; i < n; i++) {
              s += i * i;
          }
          return s;
      }
      
    • int h(int n) {
          if (n == 0) {
              return 1;
          }
          return h(n - 1) * n;
      }
      
  3. Найдите асимптотики, за которые работают эффективные алгоритмы, решающие данные задачи:
    • написать числа от $1$ до $N$;
    • написать все тройки чисел от $1$ до $N$;
    • найти разницу между максимумом и минимумом в массиве длины $N$;
    • найти число единиц в бинарной записи числа $N$.



Автор конспекта: Полина Романченко

По всем вопросам пишите в telegram @Romanchenko