Понимание функции времени работы

Question

Я занимаюсь самостоятельным изучением для сложного экзамена (для меня), и я не могу понять концепцию времени выполнения алгоритмов с использованием функции T (n).

Например: расчет

i = 1;     // c1 1 

sum = 0;    // c2 1 

while (i <= n) {  // c3 n+1 

    i = i + 1;   // c4 n 

    sum = sum + i;  // c5 n 

} 

Стоимость:

Total Cost = c1 + c2 + (n+1).c3 + n.c4 + n.c5 

T(n) = an^2 + bn + c 

ли найти общую стоимость достаточно?

Пожалуйста, голось с моей пустотой, любые ресурсы также будут полезны.

Answer 1

Поиск точного времени работы обычно бесполезен, так как это зависит от многих факторов, включая оптимизацию вашего компилятора, вашу аппаратную архитектуру, количество запущенных вами программ, вашу ОС и т. Д. \
Простой пример: Сколько времени это займет:

for (int i = 0; i < 16; i++) 
    c[i] = a[i] + b[i]'` 

Ответ - это зависит. Например, многие современные машины допускают добавление векторов в одну команду, которая занимает значительно меньше, чем итерация и добавление.

По указанной выше причине, мы редко заботимся о точном теоретическому времени, и нам этот big O notation вместо этого, или в качестве альтернативы - сравнить ход какой-то алгоритм, основанный на их фактической производительности - используя statistical tests.

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