Оценки времени выполнения для разных алгоритмов

Обозначим T(N) - время выполнения алгоритма. Пусть исследуемый алгоритм имеет вид:

1. набор инструкций, включающих только базовые операции:

statement 1;
...
statement k;

Тогда T(N) = T(statement 1) +... + T(statement k).

Т.к. каждая инструкция включает только базовые операции, то время выполнения этого куска кода не зависит от размера входных данных (не растет с ростом размера входных данных), т.е. является константой. Этот алгоритм имеет сложность O(1).

2. if-else инструкции

if (condition) {
sequence of statements 1
}
else {
sequence of statements 2
}

Здесь выполнится либо sequence of statements 1, либо sequence of statements 2, поэтому, т.к. мы хотим получить оценку времени выполнения в наихудшем случае, T(N) = max(T(sequence of statements 1), T(sequence of statements 2)). Например, если время выполнения sequence of statements 1 будет O(N), а sequence of statements - O(1), то T(N) = O(N).

3. Циклы.

for (i = 0; i < N; i++) {
sequence of statements
}

Т.к. цикл выполнится N раз, то sequence of statements тоже выполнится N раз. Если T(sequence of statements) = O(1), то T(N) = O(N)*O(1) = O(N).

4. Вложенные циклы.

for (i = 0; i < N; i++) {
for (j = 0; j < M; j ++){
...
}
}

Внешний цикл выполняется N раз. Каждый раз, когда выполняется внешний цикл, выполняется внутренний цикл M<N раз. Если мы хотим получить оценку времени выполнения в наихудшем случае, то T (N)= O (M ∗ N)= O (N 2), если M < N.

Теперь рассмотрим такой код:

for (i = 0; i < N; i++) {
for (j = i + 1; j < N; j ++){
sequence of statements
}
}

Посмотрим на изменение количества итераций внутреннего цикла в зависимости от итерации внешнего цикла.

i цикл j (кол-во раз выполнения)
0 N
1 N-1
2 N-2
...
N-1 1

Тогда sequence of statements выполнится N + N-1 +... + 1 раз. Для быстрого подсчета подобных сумм пригодятся формулы из матанализа, в данном случае формула

Т.е. этот алгоритм будет иметь сложность O (N 2).

А вот и другие наиболее часто нужные формулы, полезные для подобных случаев:

4. Когда утверждение включает вызов метода, то оценка времени выполнения утверждения рассчитывается с учетом оценки времени выполнения метода. Например:

for (j = 0; j < N; j ++){

g(N);

}

Если время выполнения метода g (N)= O (N), то T (N)= O (N)∗ O (N)= O (N 2).

5. Двоичный(бинарный) поиск.

int l = 0;
int u = A.length - 1
int m;
while (l <= u) {
m = l + (u - 1)/2
if A[m] < k {
l = m +1;
}
else if A[m] == k {
return m;
}
else{
u = m - 1;
}
}
return -1;

Двоичный поиск позволяет найти индекс числа k в отсортированном массиве, если этого числа в нем нет, то возвращается -1. Сначала мы сравниваем k с числом, находящимся в середине массива. Если k меньше этого числа, то дальше мы должны искать его в левой половине массива, если больше - то в правой половине. Далее k сравнивается с числом, находящимся в середине выбранной на предыдущем шаге половины массива и т.д. С каждой итерацией пространство поиска сужается вдвое. Возникает вопрос: сколько итераций необходимо будет проделать в наихудшем случае (т.е. когда в массиве так и не будет найдено число, равное k и не останется данных для сравнения).

Мы видим, что после 1 итерации останется N /2 данных для поиска индекса k, после 2 итерации останется N /4 данных, после 3 итерации - N /8 и т.д. Мы узнаем количество итераций в наихудшем случае, если решим уравнение N 2 x =1. Это уравнение равносильно уравнению 2 x = N, отсюда x = log 2(N) или x = lg (N) (см. определение логарифма). Поэтому оценка сложности алгоритма бинарного поиска - O (logN).

Хорошая новость заключается в том, что для характеризации времени выполнения большинства алгоритмов достаточно всего нескольких функций: 1, logN, N, NlogN, N 2, N 3,2 N. На графике проиллюстрированы различные скорости роста времени выполнения алгоритма в зависимости от размера входных данных:

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

Дата добавления: 2015-07-11