随机访问迭代器的复杂性

我想检查迭代n个元素的数组是否具有复杂度O（n）？为了对抗编译器优化，我通过{-1,1，-1,1 ...}初始化数组，然后计算所有元素的总和。这里是代码：随机访问迭代器的复杂性

#include <iostream> 
#include <chrono> 
#include <string> 
#include <vector> 
using namespace std; 
const int numIter = 1000; 
chrono::system_clock::time_point getTime() 
{ 
    return std::chrono::high_resolution_clock::now(); 
} 
void showDeltaT(const string& text, const std::chrono::system_clock::time_point& t1, std::chrono::system_clock::time_point& t2) 
{ 
    cout << 
     text << 
     std::chrono::duration_cast<std::chrono::milliseconds>(t2 - t1).count() << 
     " milliseconds" << 
     "\n" 
     ; 
} 
void test(int size) 
{ 
    cout << "test for size " << size << "\n"; 
    std::vector<int> array(size); 
    for (int i = 0; i < size; i++) 
    { 
     array[i] = i % 2 ? 1 : -1; 
    } 
    auto t1 = getTime(); 
    int s = 0; 
    for (int i = 0; i < numIter; i++) 
    { 
     for (int k = 0; k < size; k++) 
     { 
      s += array[k]; 
     } 
    } 
    auto t2 = getTime(); 
    showDeltaT("the sum is: " + to_string(s) + " and the time is ", t1, t2); 
    cout << endl; 

} 
void main() 
{ 
    test((int)1.e6); 
    test((int)2.e6); 
    test((int)3.e6); 
    test((int)4.e6); 
    test((int)5.e6); 
    test((int)6.e6); 
    test((int)7.e6); 
    test((int)8.e6); 
    test((int)9.e6); 
    test((int)10.e6); 
    getchar(); 
}

令人惊讶的是，我没有得到预期的结果。看来时间非线性增加：

试验大小百万总和为：0，时间为121毫秒

试验大小2000000 总和为：0，时间为316毫秒

试验大小3000000 总和为：0，时间为580毫秒

试验大小4000000 总和为：0，时间为828毫秒

试验大小5000000 总和为：0和时间是1063毫秒

试验大小6000000 总和为：0和时间是1285毫秒

试验大小7000000 总和：0和时间是1521毫秒

试验大小8000000 总和为：0和时间是1756毫秒

试验大小9000000 总和：0，时间为1998年毫秒

测试尺寸千万总和：0，时间为2260毫秒

你能解释这样的行为？

更新：正如在评论中提到的，依赖性实际上是线性的。是的，这是真的：

现在新的问题出现了：为什么它的延长不通过（0,0）？

来源

2016-03-01 David

这对我来说看起来很线性。你有图表吗？ – Galik

我把数字放入LibreOffice并制作了一张图表：http://imagebin.ca/v/2YkHiaGEjfLr – Galik

@Galik谢谢。你是对的。请参阅问题的更新 – David

我的猜测是时间分辨率（毫秒）是小到精确的方式。来自外部的任何“污染”（执行某些其他任务的操作系统）都会使结果出轨......尝试更严格的操作，并请执行相同测试时的执行时间（例如，对于100k个元素，然后执行三次）做一个意思）。如果你真的想衡量性能看看这个例子：

http://web.cse.ohio-state.edu/~teodores/download/teaching/cse675.au08/CSE675.02.Performance.pdf

来源

2016-03-01 11:41:09 asalic

随机访问迭代器的复杂性

回答

相关问题