java - 如何确定看起来像这样的大 O : (x -1) + (x - 2) + (x - 3) . .. (x - x)

Question

我正在努力温习我的大计算。如果我有将所有项目移至 '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。但什么是？？？我不知道公式中的变量应该填什么。我什至不知道我是否走在正确的道路上。又名我忘记了如何做数学:(

Answer 1

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

只需将以下内容重写为:

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

等于:(n(n+1)/2 - n)。

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

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