反转数组的运行时间复杂度是多少？

Question

为什么这个逻辑的运行时间复杂度是O(N)？迭代次数仅为一半。请解释！

for(int i = 0; i < validData.length / 2; i++)
{
    int temp = validData[i];
    validData[i] = validData[validData.length - i - 1];
    validData[validData.length - i - 1] = temp;
}

- chetan chouhan

---

随着元素数量的增加，复杂度呈线性增长。如果将 N 增加一倍，循环次数也会增加一倍。 - AJNeufeld

Answer 1

大O表示法关注的是数量级和复杂度如何与元素数量相关。 O(1/2 * n) == O(n)

- Andrew Jenkins

---

实际上，这不是关于“数量级”的问题。 - Stephen C

Answer 2

时间复杂度分为以下几类：时间复杂度分类:

• 常数阶（O(1)）
• 对数阶（O(log(N))）
• 线性阶（O(N)）
• 平方阶（O(N^2)）
• 立方阶（O(N^3)）
• 等等...

因为在您的情况中，将 1/2 视为常数（尤其是考虑到高值N时），所以O(N)是O(N/2)复杂度的一般近似。

因此，最终的复杂度被认为是线性的（仅取决于 N 的值：最终执行时间与 N 成线性增长）。

- aUserHimself

Answer 3

我们对算法在输入规模增长时的扩展性感兴趣，而常数在理论上不会对其行为产生很大影响。

因此，即使您在处理数组的一半 O(1/2 * n)，在理论上它仍然是 O(n)。

- mrhallak