Я ассистент профессора в местном университете на алгоритмы и структуры данных курсов. Я сделаю все возможное , чтобы объяснить это здесь , на простых условиях, но имейте в виду , что эта тема занимает мои студенты пару месяцев , чтобы наконец -то понять. Вы можете найти более подробную информацию о главе 2 Структуры данных и алгоритмы в Java книги.
Там нет механической процедуры , которая может быть использована для получения BigOh.
Как «поваренная книга», чтобы получить BigOh из куска кода, в первую очередь необходимо понимать , что вы создаете математическую формулу , чтобы подсчитать , сколько шагов вычислений получить казнили данный вход некоторого размера.
Цель проста: сравнить алгоритмы с теоретической точки зрения, без необходимости выполнения кода. Чем меньше число шагов, тем быстрее алгоритм.
Например, предположим, что у вас есть этот кусок кода:
int sum(int* data, int N) {
int result = 0; // 1
for (int i = 0; i < N; i++) { // 2
result += data[i]; // 3
}
return result; // 4
}
Эта функция возвращает сумму всех элементов массива, и мы хотим , чтобы создать формулу для подсчета вычислительной сложности этой функции:
Number_Of_Steps = f(N)
Таким образом , у нас есть f(N)
, функция для подсчета числа вычислительных шагов. Вход функции является размером структуры для обработки. Это означает , что эта функция вызывается , например , как:
Number_Of_Steps = f(data.length)
Параметр N
принимает data.length
значение. Теперь нам нужно фактическое определение функции f()
. Это делается из исходного кода, в котором каждая линия интересна , пронумерованных от 1 до 4.
Есть много способов , чтобы вычислить BigOh. С этого момента мы будем считать , что каждое предложение , которое не зависит от размера входных данных занимает постоянное C
число вычислительных шагов.
Мы собираемся добавить индивидуальный номер шагов функции, и ни локальные переменные , ни оператор возврата зависит от размера data
массива.
Это означает, что линии 1 и 4 принимают количество C шагов каждых, а функция несколько, как это:
f(N) = C + ??? + C
Следующая часть , чтобы определить значение for
заявления. Помните , что мы рассчитываем количество вычислительных шагов, а это означает , что тело for
заявления запускается на выполнение N
раз. Это то же самое, добавив C
, N
раз:
f(N) = C + (C + C + ... + C) + C = C + N * C + C
Там нет никакого механического правило посчитать , сколько раз тело из for
запускается на выполнение, вы должны считать это смотря на то , что делает делать код. Для упрощения расчетов, мы игнорируем переменную инициализации, состояние и инкремент часть for
заявления.
Для того, чтобы получить фактическую BigOh нам нужен асимптотический анализ функции. Это примерно как это делается:
- Заберите все константы
C
.
- От
f()
получить полином в своем standard form
.
- Разделить условия и полином сортировать их по темпам роста.
- Держите тот , который становится все больше , когда
N
подходы infinity
.
Наши f()
два условия:
f(N) = 2 * C * N ^ 0 + 1 * C * N ^ 1
Забирая все C
константы и избыточные части:
f(N) = 1 + N ^ 1
Так как последний член является тот , который растет больше , когда f()
приближается к бесконечности (думаю , что на границах ) это аргумент BigOh, а sum()
функция имеет BigOh из:
O(N)
Есть несколько трюков , чтобы решить некоторые сложные из них: использование сложений всякий раз , когда вы можете.
В качестве примера, этот код может быть легко решена с помощью сложений:
for (i = 0; i < 2*n; i += 2) { // 1
for (j=n; j > i; j--) { // 2
foo(); // 3
}
}
Первое , что нужно спросить является порядок исполнения foo()
. В то время как обычно должна быть O(1)
, вы должны спросить ваши профессор об этом. O(1)
средство (почти, в основном) постоянное C
, не зависящее от размера N
.
for
Заявление на номер один предложение сложно. В то время как индекс заканчивается 2 * N
, приращение делается на два. Это означает , что первый for
получает выполняются только N
шаги, и мы должны разделить счет на две части .
f(N) = Summation(i from 1 to 2 * N / 2)( ... ) =
= Summation(i from 1 to N)( ... )
Предложение номер два еще сложнее , так как это зависит от значения i
. Взгляните: индекс я принимает значение: 0, 2, 4, 6, 8, ..., 2 * N, а второй for
получить исполненный: N раз первый, N - 2 вторых, N - 4 третий ... до стадии N / 2, на которой второй for
никогда не будет выполнен.
В формуле, это означает, что:
f(N) = Summation(i from 1 to N)( Summation(j = ???)( ) )
Опять же , мы рассчитываем количество шагов . И по определению, каждое суммирование должно всегда начинаться с одного и заканчивается на ряд больше или равно , чем один.
f(N) = Summation(i from 1 to N)( Summation(j = 1 to (N - (i - 1) * 2)( C ) )
(Мы предполагаем , что foo()
это O(1)
и принимают C
меры.)
У нас есть проблема здесь: когда i
принимает значение N / 2 + 1
вверх, внутреннее Суммирование заканчивается отрицательным число! Это невозможно и неправильно. Нам нужно разделить на две части суммирования, будучи переломным моментом в тот момент i
занимает N / 2 + 1
.
f(N) = Summation(i from 1 to N / 2)( Summation(j = 1 to (N - (i - 1) * 2)) * ( C ) ) + Summation(i from 1 to N / 2) * ( C )
Поскольку ключевой момент i > N / 2
, внутренний for
не будут выполнены, и мы предполагаем , постоянная сложность выполнения C на его теле.
Теперь сложения можно упростить, используя некоторые правила удостоверения:
- Суммирование (вес от 1 до N) (С) = Н * С
- Суммирование (вес от 1 до N) (A (+/-), B) = Суммирование (вес от 1 до N) (A) (+/-) Суммирование (вес от 1 до N) (B)
- Суммирование (вес от 1 до N) (ш * С) = С * Суммирование (вес от 1 до N) (ж) (С является константой, независимой от
w
)
- Суммирование (вес от 1 до N) (ш) = (N * (N + 1)) / 2
Применяя некоторую алгебру:
f(N) = Summation(i from 1 to N / 2)( (N - (i - 1) * 2) * ( C ) ) + (N / 2)( C )
f(N) = C * Summation(i from 1 to N / 2)( (N - (i - 1) * 2)) + (N / 2)( C )
f(N) = C * (Summation(i from 1 to N / 2)( N ) - Summation(i from 1 to N / 2)( (i - 1) * 2)) + (N / 2)( C )
f(N) = C * (( N ^ 2 / 2 ) - 2 * Summation(i from 1 to N / 2)( i - 1 )) + (N / 2)( C )
=> Summation(i from 1 to N / 2)( i - 1 ) = Summation(i from 1 to N / 2 - 1)( i )
f(N) = C * (( N ^ 2 / 2 ) - 2 * Summation(i from 1 to N / 2 - 1)( i )) + (N / 2)( C )
f(N) = C * (( N ^ 2 / 2 ) - 2 * ( (N / 2 - 1) * (N / 2 - 1 + 1) / 2) ) + (N / 2)( C )
=> (N / 2 - 1) * (N / 2 - 1 + 1) / 2 =
(N / 2 - 1) * (N / 2) / 2 =
((N ^ 2 / 4) - (N / 2)) / 2 =
(N ^ 2 / 8) - (N / 4)
f(N) = C * (( N ^ 2 / 2 ) - 2 * ( (N ^ 2 / 8) - (N / 4) )) + (N / 2)( C )
f(N) = C * (( N ^ 2 / 2 ) - ( (N ^ 2 / 4) - (N / 2) )) + (N / 2)( C )
f(N) = C * (( N ^ 2 / 2 ) - (N ^ 2 / 4) + (N / 2)) + (N / 2)( C )
f(N) = C * ( N ^ 2 / 4 ) + C * (N / 2) + C * (N / 2)
f(N) = C * ( N ^ 2 / 4 ) + 2 * C * (N / 2)
f(N) = C * ( N ^ 2 / 4 ) + C * N
f(N) = C * 1/4 * N ^ 2 + C * N
И BigOh является:
O(N²)