есть алгоритм:
Type ScalarProduct(Type v1[], Type v2[], int n)
{
int i = 0;
Type sum = 0;
for (i = 0; i < n; i++)
sum += v1[i] * v2[i];
return sum;
}
высчитывающий скалярное произведение двух векторов размерности N,нужно было провести серию экспериментов, в которых будет фиксироваться время работы программы для различных значений n
Серию результатов эксперимента предлагаю:
- N=1000,t=0.001
- N=2000,t=0.014
- N=5000,t=0.046
- N=10000,t=0.004
- N=20000,t=0.001
- N=50000,t=0.064
- N=100тыс, t=0.002
- N=200тыс, t=0.002
- N=500тыс, t=0.005
Вопрос: разве может алгоритм при N=500 тысяч, работать быстрее, чем,например при N=2000?????
Алгоритм, если я правильно разобрался, имеет сложность вида О(n), но на графике, очевидно, никакой линейности не наблюдается.
Способ реализации подсчёта времени работы алгоритма прилагаю:
clock_t start = clock();
cout << ScalarProduct <int>(vect1, vect2, N) << "\n";
clock_t end = clock();
cout << "Completed for " << (double)(end - start) / CLOCKS_PER_SEC << " second" << endl;
Массивы vect1 и vect2 заполняются рандомно.
cout << ScalarProduct <int>(vect1, vect2, N) << "\n";
предположу, что на небольшом количестве данных, основное время уходит на вывод в консоль