Сложность времени в Big-O

Question

Что будет временем BigO этого алгоритма

Input: Array A sorting n>=1 integers
Output: The sum of the elements at even cells in A
s=A[0]
for i=2 to n-1 by increments of 2
{
s=s+A[i]
}
return s

Я думаю, что функция для этого уравнения F (n) = n * потолок (n / 2), но как вы можете преобразовать это в bigO

Answer 1

Временная сложность для этого алгоритма будет O(n), так как объем работы, которую он выполняет, растет линейно с размером входных данных.Другой способ взглянуть на это состоит в том, что один раз зацикливается на входе - игнорируйте тот факт, что он просматривает только половину значений, что не имеет значения для сложности Big-O)

Answer 2

Количество операций не пропорционально n*ceiling(n/2), а скорее n/2, что составляет O(n). Из-за значения big-O (которое включает в себя идею произвольного коэффициента), O(n) и O(n/2) абсолютно эквивалентны - поэтому он всегда записывается как O(n).

Answer 3

Это алгоритм O (n), поскольку вы смотрите на ~ n / 2 элемента.

Answer 4

Формальный способ получения точного количества операций и порядка роста вашего алгоритма:

Answer 5

Ваш алгоритм выполнит N / 2 итерации, если в массиве есть N элементов.Каждая итерация требует постоянного времени для завершения.Это дает нам O (N) сложность, и вот почему.

Как правило, время выполнения алгоритма является функцией f (x) от размера данных.Сказать, что f (x) есть O (g (x)), означает, что существует некоторая постоянная c, такая что для всех достаточно больших значений xf (x) <= cg (x).Легко видеть, как это применимо в нашем случае: если мы предположим, что каждая итерация занимает единицу времени, очевидно, f (N) <= 1 / 2N.</p>