如何确定像这样的东西的大O：(x -1) + (x - 2) + (x - 3) ...(x - x)
如何确定像这样的东西的大O：(x -1) + (x - 2) + (x - 3) ...(x - x)
提问于 2012-09-30 01:29:55
我正在努力复习我的大o计算。如果我有一个将所有项目移到'i‘2空格右边的函数，我有一个公式，看起来像这样：
(n -1) + (n - 2) + (n - 3) ... (n - n)其中第一次迭代我必须移动(x-1)个项，第二次(x-2)个项，依此类推……方法：
int[] s = {1,2,3,4, , }
public static char[] moveStringDownTwoSpaces(char[] s){
for(int j = 0; j < s.length; j++){
for(int i = s.length-3; i > j; i--){
s[i+2] = s[i];
}
return s;
}
}我知道这是O(n^2)，但我不太理解转换它背后的数学：
(n -1) + (n - 2) + (n - 3) ... (n - n)进入到这个
O(n^2)在我看来，如果n=5(字符串的长度为5)，我会...
(5-1) + (5-2) + (5-3) + (5-4) + (5-5) = 5(5 - ???)这就是
(n-1) + (n-2) + (n-3) + (n-4) + (n-5) = n(n - ???)所以我得到了5*5 = 25，这是n^2。但是什么是？我不知道如何表示公式中的变量。我甚至不知道我是不是走对了路。我忘了怎么做数学了:(
回答 2
Stack Overflow用户
回答已采纳
发布于 2012-09-30 01:37:29
(n -1) + (n - 2) + (n - 3) ... (n - n)只需重写以下代码：
1 + 2 + 3 + ....+ (n-1)它等于：(n(n+1)/2 - n)。
现在您可以看到它是O(n^2)。
正如@hvd所指出的，您可能希望将return语句放在循环之外。
Stack Overflow用户
发布于 2012-09-30 01:42:19
Big-O符号不是确切的上限。这是一个渐近的上界。在许多情况下，算法可能看起来像O(n^2)，但分期分析可能显示出线性阶复杂性。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/12654834
复制相关文章
相似问题
腾讯云开发者
