c++ - 如何从理论上计算嵌套循环的运行时间？

Question

<分区>

Answer 1

如果你只是要求测量你可以使用的时间

#include <ctime>

int start_s=clock();
    // code
int stop_s=clock();
cout << "time (in milis): " << (stop_s-start_s)/double(CLOCKS_PER_SEC)*1000;

但如果您想知道如果获得更多 ram 或更多 cpu 内核，这个运行时是否会更好，这就是您所需要的:

简短的回答:它取决于“//执行某事” block

长答案: 它不直接取决于循环边界是什么，它只取决于你在嵌套循环中做了什么 这里有一些双循环的例子来证明这一点

如果你正在处理公式，那么使用更高的 cpu 频率会更好

请注意，核心数与运行时间无关，因为默认情况下代码未并行化

sum = 0;
for(i=0;i<10000000;i++)
    for(j=0;j<999999;j++)
        sum+=1;

如果你正在处理数组，那么你的 RAM 可以使用 spatial/temporal locality但是保存在内存中的数组部分受到其他参数的限制，因此更大的 RAM 不会做太多但使用更高的 RAM 频率会更好

int arr[10000000][999999];
arr[0][0] = 0;
for(i=1;i<10000000;i++)
    for(j=1;j<999999;j++)
        arr[i][j]=arr[i-1][j-1];

如果您正在处理磁盘/缓冲区操作，那么您的 RAM 或 cpu 都无法对其进行超过一定程度的优化 - 硬件是瓶颈 -

    for(i=0;i<10000000;i++)
        for(j=0;j<999999;j++)
            cout << "yes";

    ofstream file;
    file.open ("out.txt");
    for(i=0;i<10000000;i++)
        for(j=0;j<999999;j++)
            file << "Writing to the file.\n";