0
Если у меня есть массив из 1 миллиона целых чисел. Подведение итогов считается O (n), потому что я должен выполнить операции добавления n-1. Правильно?Оценка Big O для суммирования массива
A
ответ
4
Если вы можете добавить два элемента в O (1), то суммирование n элементов займет O (n), да. Если они могут занять больше времени, то нет. Например, если все элементы представляют собой неподписанные 32-битные целые числа, но вы хотите точную сумму (а не сумму mod 2), тогда она может достигать n & middot; (2 − 1), в этом случае суммирование будет принимать O (n log n).
3
Да. Это точно.
Конечно, могут быть особые случаи, когда это меньше. И некоторые методы могут сделать его меньше, но эти методы имеют большие накладные расходы, чем добавление.
Например, если вы знаете, что значения от 1 до n, это O (1), потому что вы можете вычислить n * (n + 1)/2. Но общий случай O (n).
+1
Вычисление n * (n-1)/2 принимает O (log n), а не O (1). – Charles
+0
Как вы оцениваете? Это несколько умножений и вычитание. Независимо от n, это займет столько же времени, если нет переполнения. – JoshD
+0
Это O (1), если n равно 1, для вычисления n * (n + 1)/2 потребуется столько же времени, как и n, равное 1 миллиону. Поэтому он не зависит от N: O (1) time [constant] –
0
Да, поскольку время, используемое для суммирования, является прямым изменением числа элементов n.
Spot on, chap! _ –
Этот вопрос, вероятно, лучше подходит для http://cstheory.stackexchange.com/ – joschi
@joshi: Я не знаю. Я думаю, что это идеальный вопрос SO, а stackexchange слишком фрагментирован ... – Thilo