c - 程序的运行时近似公式

Question

我有一个C程序，它在以下时间内执行以下数量的输入：

23           0.001s            
100          0.001s          

我试图为此找到一个公式，但没有成功。据我所知，时间有时会加倍，有时不会，这就是为什么我找不到这个公式的原因。

有什么想法吗？

笔记

1）我在 CPU 时间（用户+系统）中测量这个。

2）我的程序使用快速排序

2) 我的程序的渐近运行时分析/复杂度是 O(NlogN)

Answer 1

绘制这个看起来很像你正在触及“缓存悬崖” - 你的数据足够大，以至于它并不完全适合 cpu 缓存级别，因此必须在更便宜和更昂贵的级别之间交换数据

较低级别的差异可能是由于精度 - 如果您增加计时器块内的循环 - 这可能会平滑

通常，当遇到缓存悬崖时，eprformace 类似于绘制 O*Q

其中 O 是平均运行时间——在你的情况下是 Nlog(N)

Q 是一个阶跃函数，随着您传递每个缓存的分配大小而增加。所以 Q=1 低于 L1 尺寸，10 高于 L1 尺寸，100 高于 L2 尺寸等（仅以数字为例）

事实上，有些人通过绘制 O(1) 函数并寻找性能悬崖峭壁时使用的内存来验证他们的缓存大小：

           ___
 _____-----
  L1 | L2 | L3

Answer 2

我总是用它来获得精确的运行时间..

#include<stdio.h>

#include <time.h>

#include <stdlib.h>

`clock_t 开始，停止；

`#define START if ( (startm = clock()) == -1) {printf("错误调用时钟");exit(1);}

`#define STOP if ( (stopm = clock()) == -1) {printf("错误调用时钟");exit(1);}

#define PRINTTIME printf( "%6.3f seconds used by the processor.", ((double)stopm-startm)/CLOCKS_PER_SEC);

`int main() {

诠释 i, x; 开始;

  scanf("%d",&x);
 for(i=0;i<10000;i++){
printf("%d\n",i);

}

 STOP;
 PRINTTIME;

}