gpt4 book ai didi

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

转载 作者:行者123 更新时间:2023-12-02 00:11:52 30 4
gpt4 key购买 nike

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

最佳答案

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

只需将以下内容重写为:

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

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

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

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

关于java - 如何确定看起来像这样的大 O : (x -1) + (x - 2) + (x - 3) . .. (x - x),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/12654834/

30 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com