0

我正在努力复习我的大计算。如果我有将所有项目移动到 '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。但什么是？？？我不知道该为公式中的变量添加什么。我什至不知道我是否会以正确的方式进行。又名我忘了怎么做数学:(

4

2 回答 2

3 
(n -1) + (n - 2) + (n - 3) ... (n - n)

只需将以下内容改写为：

1 + 2 + 3 + ....+ (n-1)

这等于：(n(n+1)/2 - n)。

现在你可以看到它是O(n^2)。

正如@hvd 所指出的，您可能希望将return语句放在循环之外。

于 2012-09-29T17:37:28.783 回答
0

Big-O 表示法不是确切的上限。这是一个渐近上界。在许多情况下，算法可能看起来像 O(n^2)，但摊销分析可能显示线性阶复杂度。

于 2012-09-29T17:42:18.920 回答