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

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]是什么。所以我有点困惑如何确定时间复杂度。如何计算此实现的时间复杂度

来源

2016-08-01 XDProgrammer

内循环将在最坏的情况下运行时间如下：第（n-1）+（N-2）+（N-3）....... +（1）其中n是字符串的长度。所以当你总结这个序列。最高的顺序是n^2。所以最坏的时间复杂度变成了O（n^2）。 – sinsuren

有此良好的记法解释假设两个环路从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

来源

2016-08-01 07:39:52

外循环第一次迭代中的比较次数为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)的复杂性。

来源

2016-08-01 07:39:00

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

回答

相关问题