Рекомендуемая литература

Дасгупта С., Пападимитриу Х., Вазирани У., «Алгоритмы»

O-символика

Что такое быстрый и что такое медленный алгоритм? Можно было бы замерять время работы готовой программы, но оно будет меняться не только от компьютера к компьютеру, но и от объема входных данных. Кроме того было бы очень удобно на этапе продумывания программы оценить какой алгоритм подходит под временные ограничения в которых он будет должен укладываться, а какой алгоритм будет работать так долго, что дождаться его результата не хватит всего времени мира.

Одной из удобных оценок времени работы алгоритма является способ оценить сколько примерно примитивных операций \(g(n)\) выполнит алгоритм в зависимости от объема входных данных \(n\). При этом не так важна точная оценка числа операций \(f(n)\) - достаточно чтобы функция-грубая оценка \(g(n)\) с ростом \(n\) росла сопоставимо с тем как растет точное число операций \(f(n)\). Чуть более строго - оценка числа операций \(g(n)\) должна расти не быстрее чем точное число операций \(f(n)\).

Для еще более точной формулировки используется так называемая \(O\)-символика:

Определение Пусть даны две функции \(f(n)\) и \(g(n)\) натурального аргумента \(n\), значениями которых являются положительные действительные числа. Говорят, что \(f(n)=O(g(n))\) (\(f\) растет не быстрее чем \(g\)), если существует такая константа \(c > 0\), что \(f(n) \lt c \cdot g(n)\) для всех натуральных \(n\).

Другими словами, \(f=O(g)\) означает, что отношение \(f(n)/g(n)\) ограничено сверху некоторой константой.

Запись \(f=O(g)\) можно читать как “\(f \lt g\) с точностью до константы”.

Свойства В \(O\)-нотации верны следующие свойства:

1) Постоянные множители (коэффициенты) можно опускать. Например \(O(2n^3) = O(n^3)\)

2) \(n^a\) растет быстрее \(n^b\) при \(a > b\), поэтому можно пренебречь \(n^b\) если уже есть \(n^a\). Например \(O(n^2+n+1) = O(n^2)\)

3) Любая экпонента растет быстрее полинома, например \(3^n\) растет быстрее \(n^5\), поэтому полином можно опускать в присутствии экспоненты. Например \(O(2^n+n^{999}) = O(2^n)\)

4) Любой полином растет быстрее логарифма, например \(n\) и даже \(\sqrt{n}\) растет быстрее чем \(log^3(n)\). Например \(O(n+log(n)) = O(n)\)

Примеры асимптотики в Java

Массивы

int[] xs = new int[n]; // O(n) т.к. потребуется создать и заполнить нулями n ячеек в памяти

xs[0] = scanner.nextInt(); // O(1)

int sum = 0;
sum += xs[0]; // любая операция с примитивными типами, включая арифметику выполняется за O(1)

for (int i = 1; i < n; ++i) {
    xs[i] = scanner.nextInt(); // каждая такая строчка выполняется за O(1)
} // но в цикле (n-1) итераций, значит итого данный цикл работает за (n-1)*O(1) = O(n-1) = O(n)

Строки

Строка - это внутри попросту массив, поэтому:

String str = scanner.nextLine(); // пусть считанная строка длины n, тогда ее считывание и аллокация в памяти массива под эту строку как и с массивом выше - O(n)

str += "xyz"; // можно было бы подумать что эта операция выполняется за O(1), но на самом деле в этот момент будет создана новая строка
              // длинной n+3 и в нее положена строка str продленная этими тремя символами xyz, т.е. будет выполнено O(n+3)=O(n) операций

int m = scanner.nextInt();
for (int i = 0; i < m; ++i) {
    String part = new String(i); // число i занимает не больше 11 символов, поэтому его перевод в строчку занимает O(11)=O(1)
    
    str += part; // как и в случае с конкатенацией двух строк выше - здесь время работы O(str.length() + part.length())
                 // при этом от итерации цикла к итерации размер строки str растет от O(n) до O(n+m*11)=O(n+m)
                 // поэтому на каждой итерации O(str.length())=O(n+m)
                 // поэтому эта строка на каждой итерации занимает не больше чем O(str.length() + part.length())=O((n+m)+11)=O(n+m)
} // всего этот цикл совершает m итераций, на каждой итерации делая две операции, первая за O(1) и вторая за O(n+m)
  // поэтому весь цикл работает за O(m*(1+n+m))=O(m*n+m*m)=O(m*max(n, m))

ArrayList

ArrayList<Integer> values = new ArrayList<Integer>();

for (int i = 0; i < n; ++i) {
    values.add(scanner.nextInt()); // т.к. массив по мере исчерпания увеличивается в два раза, то это происходит редко, и в среднем данная строчка работает за O(1)
} // итого O(n)

int x = values.get(n / 2); // эта операция ничем не отличается от обычного обращения к элементу примитивного массива, поэтому выполняется за O(1)

values.add(0, scanner.nextInt()); // эта операция вставит считанное число перед бывшим первым элементом, иначе говоря - сдвинет весь массив на единицу вправо,
                                  // а на свободное первое место положит считанное число
                                  // процедура сдвига занимает столько времени сколько элементов надо скопировать, т.е. O(values.size())=O(n)

LinkedList

LinkedList<Integer> values = new LinkedList<Integer>();

for (int i = 0; i < n; ++i) {
    values.add(scanner.nextInt()); // добавить элемент - это просто у последнего звена добавить ссылку на новодобавленный объект, и запомнить этот новый объект как последнее звено, поэтому O(1) 
} // итого O(n)

int x = values.get(n / 2); // эта операция интересная, чтобы дойти до середины - надо начиная с первого элемента перейти по n/2-1 ссылке от элемента к элементу
                           // т.е. занимает O(n/2-1)=O(n)

values.add(0, scanner.nextInt()); // зато вставка в начало такая же быстрая как и в конец - достаточно создать новый элемент, у нового элемента указать ссылкой старый первый объект
                                  // и запомнить новодобавленный объект как новый первый, т.е. O(1)

Упражнения

Упр. 1 Какая асимптотика у рассчета числа Фибоначчи номер \(N\) через рекурсивную наивную реализацию?

Упр. 2 Какая асимптотика у данного кода:

int n = scanner.nextInt();
int m = scanner.nextInt();
int[] values = new int[n];
for (int i = 0; i < n; ++i) {
    values[i] = scanner.nextInt();
}
for (int i = 0; i < m; ++i) {
    int from = scanner.nextInt(); //    0 <= from <  n
    int to = scanner.nextInt();   // from  <  to  <= n
    int sum = 0;
    for (int j = from; j < to; ++j) {
        sum += values[j];
    }
    System.out.println("Сумма на [" + from + "; " + to + ") равна " + sum);
}

Упр. 3 Какая асимптотика у алгоритма умножения столбиком? В предположении что число цифр в обоих числах \(N\), и что умножить/сложить цифру с цифрой и т.п. - \(O(1)\).

Упр. 4 Какая асимптотика у алгоритма вычитания столбиком? В предположении что число цифр в числах \(N\) и \(M\), и что вычесть цифру из цифры, осуществить заимствование из старшего разряда т.п. - \(O(1)\).

Упр. 5 Какая асимптотика у данного кода:

String result = "";
for (int i = 0; i < N; ++i) {
    if (i != 0) {
        result += ", ";          // операция конкатенации двух строк A и B
    }                            // выполняется за
    result += scanner.nextInt(); // O(A.length + B.length), где A=result и B=new String(scanner.nextInt())
}

Упр. 6 Какая асимптотика у данного кода:

ArrayList<Integer> values = new ArrayList<Integer>();
for (int i = 0; i < N; ++i) {
    values.add(0, scanner.nextInt()); // выполняет вставку значения перед самым первым элементом
                                      // и тем самым сдвигая каждый элемент на один индекс
                                      // т.о. выполняется за O(values.size())
}

Упр. 7 Какая асимптотика у данного кода:

LinkedList<Integer> values = new LinkedList<Integer>();
int result = 0;
for (int i = 0; i < N; ++i) {
    for (int j = 0; j < M; ++j) {
        values.add(scanner.nextInt()); // по этой строчке и двум циклам можно опеределить какая асимптотика O(values.size())
    }
    result += values.get(values.size() / 2); // опасное место, т.к. у LinkedList операция get работает за O(values.size())
}

Упр. 8 Какая асимптотика у данного кода:

ArrayList<Integer> values = new ArrayList<Integer>();
String result = "";
for (int i = 0; i < M; ++i) {
    for (int j = 0; j < N; ++j) {
        values.add(scanner.nextInt());
    }
    if (i != 0) {
        result += ", ";
    }
    result += values.get(values.size() / 2); // ArrayList.get за O(1), но конкатенация строк - поэтому важно лишь какая длина у result
}