对于动态数组，要设置的每个元素都必须由CPU单独考虑，因此时间复杂度为O(N).
或者是吗？
但这并不是“big-oh”真正的工作原理。这也不是 CPU 真正的工作方式。
Big-oh 表示法涉及渐进的当元素数量趋于无穷大时系统的行为。这就是说：当我们将其应用于少量元素时，我们应该持保留态度！
CPU 对于少量元素和大量元素的行为也不同，因为它们具有不同的缓存级别，这意味着不同的访问延迟。你看到这个每时每刻设计高性能算法。例如，参见这一页 https://github.com/flame/how-to-optimize-gemm/wiki#blocking-to-maintain-performance描述如何优化矩阵乘法：“阻塞以保持性能”部分主要是关于重新排列计算，以便它们保留在 CPU 的缓存中。
现在，让我们更具体地谈谈你的问题。
请考虑下面每个计算机科学家应该知道的延迟数字的方便图表（source https://gist.github.com/hellerbarde/2843375).
这里的重点是（随机）主内存引用成本约为 100ns，而对 L1 缓存的引用成本为 0.5ns，对 L2 缓存的引用成本为 7ns。由于缓存效应，从 RAM 中顺序读取可显着提高速度。
这意味着，在其他条件相同的情况下，您可以从 L1 读取 200 个数字，或者从 L2 读取 14 个数字，而所用的时间与从 RAM 中读取单个数字所需的时间相同。
这让我们进入成本模型。
考虑像这样初始化两个动态数组：
std::vector<int> a(20,1);
std::vector<int> a(21,1);
根据上述内容，我们预计处理附加元素大约需要 0.5 纳秒（因为整个数组适合缓存），而将数组存储到内存则需要 100 纳秒。也就是说，添加额外元素的边际成本可以忽略不计。事实上，即使添加许多元素的边际成本也可以忽略不计（多少取决于处理器）。
让我们应用这些想法。考虑这两个陈述。
int m = array1[20];
std::vector<int> a(900,1);
如果你从一个角度思考这个问题O(1) vs. O(N)从角度来看，您可能会认为有些愚蠢的事情，例如“第二个语句将比第一个语句花费 900 倍的时间”。您可能有一个更复杂的想法是“O(N)第二个语句可能很小，因此很难知道哪个会更快”。
有了一些缓存知识，您可能会对自己说“对于这些小N值渐近分析是不合适的”。您可能进一步认为“这些语句可能需要相同的时间”或“第二个语句可能会运行faster由于缓存效应，比第一个要好”。
一个实验
我们可以用一个简单的实验来证明这一点。
以下程序初始化不同长度的数组：
#include <vector>
#include <iostream>
#include <chrono>
#include <string>
int main(int argc, char **argv){
const int len = std::stoi(std::string(argv[1]));
auto begin = std::chrono::high_resolution_clock::now();
for(int i=0;i<10000;i++){
std::vector<int> a(len,1);
(void)a;
}
auto end = std::chrono::high_resolution_clock::now();
std::cout << std::chrono::duration_cast<std::chrono::nanoseconds>(end-begin).count() << std::endl; //Nanoseconds
}
该程序运行动态数组的多次初始化，以平均由于机器上运行的其他程序而导致的波动。
我们多次运行这个程序：
for n in {1..100}; do ./a.out 1; done | awk '{print "1 "$1}' | xclip
处理由于其他程序运行而导致的程序启动和机器内存状态的差异。
在我的 Intel(R) Core(TM) i5 CPU M480 @ 2.67GHz 上，具有 32K L1 缓存、256K L2 缓存和 3072K L3 缓存，结果是这样的：
请注意，对于大约 1000 个元素，小型数组的时间增长是次线性的（与较大数组上的后续行为相结合）。这不是O(N)行为。此后，添加 10 倍以上的元素会导致消耗约 10 倍的时间。这是O(N)行为。
在我的 Intel(R) Xeon(R) CPU E5-2680 v3 @ 2.50GHz（具有 32K L1 缓存、256K L2 缓存和 30720K L3 缓存）上尝试相同的测试，得到了非常相似的结果：
底线
数组初始化位于O(N)因为它随着元素数量的增加而增长。但实际上，由于缓存的原因，cost不线性上升。因此，一个“O(1)“命令可能需要与”相同的时间O(N)“命令，取决于大小N.
