Кто-то может объяснить как Большие О работы с Суммированием?
Вы могли бы хотеть использовать итератор, если Вы собираетесь добавить/удалить объекты к вектору, в то время как Вы выполняете итерации по нему.
some_iterator = some_vector.begin();
while (some_iterator != some_vector.end())
{
if (/* some condition */)
{
some_iterator = some_vector.erase(some_iterator);
// some_iterator now positioned at the element after the deleted element
}
else
{
if (/* some other condition */)
{
some_iterator = some_vector.insert(some_iterator, some_new_value);
// some_iterator now positioned at new element
}
++some_iterator;
}
}
при использовании индексов необходимо было бы переставить объекты/вниз в массиве для обработки вставок и удалений.
5 ответов
Мое предположение состоит в том, что формулировка вопроса означает, что вы суммируете результаты некоторых вычислений, время выполнения которых пропорционально i 2 в первом случае и пропорционально log 2 i во втором случае. В обоих случаях время выполнения общего суммирования "определяется" большими значениями N в суммировании, и, таким образом, общая оценка большого О для обоих будет N * O (f), где f - функция, которую вы ' повторное суммирование.
Простейший подход, который приходит мне в голову, - это доказательство по индукции.
Для первого, по сути, вам нужно показать, что
sum (i=1 to n) i^2 < k*n^3, k > 2,n > 0
Если мы используем обобщенный принцип индукции и возьмем базовый случай n = 1 и k = 2.
мы получим 1 <2 * 1 .
Теперь, конечно, возьмем индуктивную гипотезу, тогда мы знаем, что
sum ( i = от 1 до n) i ^ 2
сумму (i = от 1 до n) i ^ 2 + (n + 1) ^ 2
Теперь покажите
k * n ^ 3 + (n + 1) ^ 2k * n ^ 3 + n ^ 2 + 2n + 1k * n ^ 3
Следовательно, наш исходный результат верен.
Для второго доказательства вам нужно показать, что
сумма (от i = от 1 до n) log_2 (i)> = k * n * log (n) , которую я оставлю в качестве упражнения для читателя;).
Главный шаг - сумма (от i = от 1 до n) log_2 (i) + log_2 (n + 1)> = k * n * log (n) + k * log (n + 1) для некоторого k, поэтому очевидно, что k равно 1.
http://en.wikipedia.org/wiki/Big_O_notation
N повторений g (m) = O (f (m)) равно O (N * f (m)) для любого f (N).
Сумма i = 1..N из i * g (i) равна O (N * f (N)) , если g (n) = O (f (n)) и f является монотонным.
Определение: g (n) = O (f (n)), если существуют некоторые c, m, поэтому для всех n> m, g (n) <= c * f (n)
Сумма для i = 1..N из i * f (i) .
Если f монотонен по i, это означает, что каждый член <= i f (N) <= N f (N). Таким образом, сумма меньше N * c * f (N) , поэтому сумма равна O (N * f (N)) (о чем свидетельствует тот же c, m, который делает g (n) = O (f (n)))
Конечно, log_2 (x) и x ^ 2 оба монотонны.
Вероятно, ваш процессор будет умножать 32-битные целые числа за постоянное время. Но big-Oh не волнует «меньше четырех миллиардов», так что, может быть, вам стоит взглянуть на алгоритмы умножения?
Согласно Вольфрам , «традиционный» алгоритм умножения - O (n 2 ). Хотя n в данном случае является количеством цифр, и, следовательно, на самом деле log (n) в фактическом числе. Итак, я должен возвести в квадрат целые числа 1..n за время O (n.log (n)). Суммирование составляет O (log (n 2 )), что, очевидно, равно O (log (n)) для общей сложности O (n.log (n)).
Так что я вполне могу поймите свое замешательство.
Σ (i = от 1 до n) i 2 = n (n + 1) (2n + 1) / 6, что равно O (n 3 ).
Обратите внимание, что (n!) 2 = (1 n) (2 (n-1)) (3 (n-2)) ... ((n-1 ) 2) (n 1)
= Π (от 1 до n) i (n + 1-i)
> = Π (от i = от 1 до n) n
[Например, потому что для каждого i = от 1 до n, (i-1) (ni)> = 0. Сравните с Graham / Knuth / Patashnik , раздел 4.4]
= n n .
Таким образом, n! > = n n / 2 , следовательно,
Σ (я = от 1 до n) журнал я = журнал Π (я = от 1 до n) я = журнал п! > = журнал n n / 2 = (n / 2) log n, то есть Ω (n log n).