渐近复杂度(这是 big-O 使用的)不依赖于常数因子,更具体地说,您可以在函数中添加/删除任何常数因子,并且它将保持等效(即 O(2n) = O(n) )。
假设一个 if 语句花费的时间是固定的,它只会给复杂性增加一个固定的因素。
“恒定的时间”是指:
- 给定元素的 if 语句所花费的时间不取决于数组中有多少其他元素
- 因此,基本上,如果它不调用以某种方式或类似方式查看数组中其他元素的函数
- 任何非函数调用 if 语句都可能没问题(除非它包含通过数组的语句,某些语言允许这样做)
因此,为每个元素调用的 2 个(恒定时间)if 语句将是 O(2n),但这等于 O(n)(嗯,它可能实际上不是 2n,更多内容在附加说明中)。
有关更多详细信息和更正式的定义,请参阅Wikipedia 。
注意:除了不依赖于常数因子之外,它也不依赖于渐近较小的项(无论 n 有多大,这些项都保持较小),例如 O(n) = O(n + sqrt(n))。而且 big-O 只是一个上限,所以说它是 O(n 9999 ) 也是正确的(尽管说在测试/考试中可能会给你 0 分)。
附加说明:不忽略常数因素时的问题是 - 什么归类为工作单元?这里没有标准定义。一种方法是使用耗时最长的操作,但确定这一点可能并不总是直截了当,也不会总是特别准确,您也无法笼统地比较不同算法的复杂性。