一个简单的循环

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

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)