时间复杂度估算方法

  • 简单语句

简单的赋值语句，读写语句，可以看作所用时间为常量记为O(1)。

  • 分支语句

    在分支语句中，以所耗费时间最多的那个分支来计算时间复杂度。

  • 循环语句

在循环语句中，每循环1次记为O(1)，循环n次时间复杂度为O(n)。

  • 嵌套循环

在嵌套循环中，时间复杂度是多个循环的叠加，如下所示：

在嵌套循环中，时间复杂度

for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) ……. O(n*n)=O(n^2)
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) for(int k=1;k<=n;i++) ……. O(n*n)=O(n^3)
for(int i=1;i<=n;i++) {for(int j=1;j<=n;j++){…..} for(int k=1;k<=n;i++){ …….}} O(nn)=O(2n^2)