一个简单的循环

以下函数查找数组中的最大元素：

int find_max(const int *array, size_t len) {
    int max = INT_MIN;
    for (size_t i = 0; i < len; i++) {
        if (max < array[i]) {
            max = array[i];
        }
    }
    return max;
}

输入大小是数组的大小，我在代码中称为 len。

让我们统计一下操作。

int max = INT_MIN;
size_t i = 0;

这两个任务只进行一次，因此这是两次操作。循环的操作是：

if (max < array[i])
i++;
max = array[i]

由于循环中有 3 个操作，并且循环完成了 n 次，我们将 3n 添加到我们现有的 2 个操作中以获得 3n + 2。所以我们的函数需要 3n + 2 操作才能找到最大值（其复杂度为 3n + 2）。这是一个多项式，其中增长最快的项是 n 的因子，因此它是 O(n)。

你可能已经注意到操作的定义不是很明确。例如，我说 if (max < array[i]) 是一个操作，但根据架构，这个语句可以编译为例如三个指令：一个内存读取，一个比较和一个分支。我还认为所有操作都是相同的，即使例如内存操作比其他操作慢，并且它们的性能会因例如缓存效果而变化很大。我也完全忽略了 return 语句，即为函数创建一个框架的事实等。最后它与复杂性分析无关，因为无论我选择计算操作的方式如何，它只会改变系数 n 因子和常数，因此结果仍然是 O(n)。