算法复杂度计算估计中基本运算的性能特征

在大多数现代CPU上,“特定指令的周期时间”的概念并不是特别有用。管道将同时处理多条指令,它们将争夺CPU内的各种资源,因此只能在周围指令的上下文中理解给定指令的性能。在处理器系列的不同型号中,细节也会有很大的不同。

对于x86:看看 Agner Fog's "Software optimization resources" .

英特尔在他们的文章数据库中有一些关于汇编实现的信息。好的是非常密集的(比如 this 600页的PDF文件),但他们有很多有趣的信息,包括一些大约延迟时间的表。还有 a table with some latency times for their 64-bit architecture ,因此,如果需要,可以搜索类似的32位。

我个人对AMD处理器的信息一无所知。谷歌可能会出现一些结果,但自从Athlon 3000天以来,我就没有使用过AMD机器,所以我没有必要去寻找这种信息。

据我所知:

添加,sub:O(log n)

malloc:O(n*m)n是分配的大小,m是以前分配的数量。
自由:O(1)(有时O(logm))。

timing analysis ,包括缓存行为。