查找缺失数字的时间复杂度 O(n)？
Time complexity O(n) for finding missing number?
我正在尝试理解时间 complexity.Someone here 提到时间复杂度是 O(n) ，请看下图： 既然是 N(N+1)/2 ，不应该它是 O(n^2) 因为 N(N+1) 在乘法？如果我误解了什么，请纠正我。
上面的代码计算 n(n+1)/2，但这并不意味着它需要时间 O(n 2)。例如，考虑以下代码：
int x = n*n;
此代码计算 n2，但它的运行时间为 O(1)。
希望对您有所帮助！
您误解了答案：当作者说 "the sum of natural numbers 1 through N is N*(N-1)/2" 时，他提供了一个封闭式表达式来计算总和 如果所有 100 个数字都存在 。该值在 O(1) 中计算。
从给定的列表中计算 99 个数字的总和需要 O(N)。
复杂性是算法所需资源的度量。在这种情况下，如果列表的大小 n 加倍，则所需时间也会加倍。换句话说，所需的时间资源与 n 成正比。这表示为 O(n)。每一步需要多长时间都无关紧要；唯一重要的是与输入相关的总时间。
我正在尝试理解时间 complexity.Someone here 提到时间复杂度是 O(n) ，请看下图： 既然是 N(N+1)/2 ，不应该它是 O(n^2) 因为 N(N+1) 在乘法？如果我误解了什么，请纠正我。
上面的代码计算 n(n+1)/2，但这并不意味着它需要时间 O(n 2)。例如，考虑以下代码：
int x = n*n;
此代码计算 n2，但它的运行时间为 O(1)。
希望对您有所帮助！
您误解了答案：当作者说 "the sum of natural numbers 1 through N is N*(N-1)/2" 时，他提供了一个封闭式表达式来计算总和 如果所有 100 个数字都存在 。该值在 O(1) 中计算。
从给定的列表中计算 99 个数字的总和需要 O(N)。
复杂性是算法所需资源的度量。在这种情况下，如果列表的大小 n 加倍，则所需时间也会加倍。换句话说，所需的时间资源与 n 成正比。这表示为 O(n)。每一步需要多长时间都无关紧要；唯一重要的是与输入相关的总时间。