Возьмем следующий алгоритм сортировки вставками:
Я знаю, что это O (n ^ 2) довольно легко, изучив его. Но что касается доказательства, что это O(n^2), как мне это сделать? Я мог бы сложить все операции, но, насколько мне известно, n + "sum of j=2 to n" на самом деле не даст n^2.
Я действительно не вижу, как это точно доказать. Может ли кто-нибудь попытаться четко объяснить, как я могу это доказать, чтобы это работало и для алгоритма O (n ^ 3)?
Вы доказываете большую сложность O, учитывая, сколько операций выполняется в наихудшем случае. Вы выполнили часть подсчета и ввели результаты в правую колонку вашего изображения, так что остается доказать, что доминирующим термином является O(n^2).
Помимо терминов, включающих сумму, ваша программа состоит из инструкций, которые выполняются n-1 раза, так что все они являются O(n) терминами.
Теперь о терминах с суммой. В худшем случае t_j может быть j, потому что вы можете в конечном итоге уменьшить i, которое вы установили на j, вплоть до 0. Таким образом, в этом худшем случае у нас есть t_j = j, а затем у вас есть термин с sum from 2 to n of j, который равен O(n^2). Это связано с соблюдением математического тождества:
Это можно доказать, просуммировав два из этих рядов вместе, обратив внимание на то, чтобы вы добавили два члена, сумма которых равна n+1 вместе, а затем разделив сумму на два. Взгляните на доказательство в вольфраме.
Наконец, поскольку O((n^2 + n)/2) = O(n^2) вы получаете, что термины, включающие сумму, доминируют во время выполнения, и поэтому алгоритм O(n^2)
Это O(n^2), потому что у вас есть умножение, а не сумма. Возьмем, к примеру, массив, отсортированный в обратном порядке:
10 9 8 7 6 5 4 3 2 1
В этих случаях каждая итерация внутреннего цикла будет сканировать и сдвигать всю отсортированную часть массива перед вставкой следующего элемента. Это дает сортировке вставками квадратичное время выполнения (т.е. O(n2)).
Лучший способ понять сложность — попытаться найти пример наихудшего случая и следовать шагам алгоритма.
Предположение 1: если процедура P запускается не более T раз, и каждый раз P выполняется за O(f(N)), то общее время выполнения равно O(T*f(N))
Предположение 2: если процедура P выполняется за время O(f(N)) и процедура Q выполняется за время O(g(N)), то выполнение P с последующим Q требует O(f(N)) f(N) + g(N)) время.
Чтобы быть педантичным, предположение 1 следует из предположения 2, если хотите.
Предположение 3. Присваивания и арифметические операции — это O(1) операций.
Объедините эти три предположения, и вы получите результат.
Строки 6 и 7 выполняются за время O(1) и O(1) соответственно, поэтому вместе они выполняются за время O(1 + 1) = O(1). (По предположению 3 и 2)
Строка 5 определяет, что {6,7} будет выполняться не более чем A.Length - 0 раз, поэтому время выполнения {5,6,7} равно O(A.Length * 1) = O(A.Length) (By Предположение 1)
Строки 2, 4 и 8 выполняются за время O(1), поэтому {2,4,5,6,7,8} выполняется за время O(1 + 1 + A.Length + 1) = O(A.Length) время. (По предположению 3 и 2 снова)
Строка 1 определяет, что {2..8} будет выполняться не более A.Length раз, поэтому время выполнения для строк {1..8} равно O(A.Length * A.Length) = O(A.Length ^2 ) (по предположению 1).
