如何计算此实现的时间复杂度

Question

 boolean isUnique(String s){
        char [] temp = s.toCharArray();

        for(int i = 0; i < temp.length; i++){
            for(int j = i+1; j < temp.length; j++){
                if(temp[i] == temp[j]){
                    return false;
                }
            }
        }

        return true;
    }

这只是为了检查字符串中的所有字符是否唯一。我从其他例子中了解到，对于内部循环，它通常是 O(n^2)，但在这种情况下，内部循环不是从索引 0 开始。它从下一个元素开始，无论 temp[i] 是什么。所以我有点混淆如何确定时间复杂度。

Answer 1

外循环第一次迭代的比较次数为n。在第二个中它是 n-1，依此类推直到 0。所以我们有一个总和：

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

等于

n * (n + 1) / 2

也就是

(n^2 + n) * 1/2

因为 1/2 只是常数，而 n^2 增长得比 n 快，我们认为复杂度为 O(n^2)。

Answer 2

对此有很好的符号解释假设两个循环都从 0 开始说 8 你的 temp.length，然后这样想象它

O O O O O O O O
O O O O O O O O
O O O O O O O O
O O O O O O O O
O O O O O O O O
O O O O O O O O
O O O O O O O O
O O O O O O O O

所以数一数这里o的个数，他们加起来是o(n^2)

现在来看看你的情况外循环从 0 开始，内循环每次都从那开始直到结束，所以

0 0 0 0 0 0 0 0 // 0+7
0 0 0 0 0 0 0   // 1+6
0 0 0 0 0 0    //2+5
0 0 0 0 0      //3+4
0 0 0 0       //4+3
0 0 0        // 5+2
0 0          //6+1
0            //7+0

数一下这里0的个数，是(n^2)/2，也就是o(n^2)本身

第一列代表外循环，后面代表内循环的迭代次数

说明//First loop count + second loop iterations

如何计算此实现的时间复杂度

How to compute time complexity of this implementation

big-o

time-complexity