时间复杂度

O(1)

O(1) 只是常量级时间复杂度的一种表示方法，并不是指只执行了一行代码。
比如下面这行代码，它的时间复杂度也是 O(1)：

int i = 8;
 int j = 6;
 int sum = i + j;

只要代码的执行时间不随n的增大而增长，这样的代码时间复杂度都是 O(1) 级别。
或者说，一般情况下，只要算法中没有出现循环、递归语句，即使成千上万的代码也是 O(1) 级别的时间复杂度。

O(n)

线性阶时间复杂度。这种时间复杂度非常常见，只要看到有一层循环或递归的语句，所有代码的执行时间就跟每行代码的执行时间成正比关系。

int cal(int n) {
   int sum = 0;
   int i = 1;
   for (; i <= n; ++i) {
     sum = sum + i;
   }
   return sum;
 }

O(_n_2)

平方阶时间复杂度。常出现于嵌套的循环之中。

int cal(int n) {
   int sum = 0;
   int i = 1;
   int j = 1;
   for (; i <= n; ++i) {
     j = 1;
     for (; j <= n; ++j) {
       sum = sum +  i * j;
     }
   }
 }

第一个 for 循环执行了 n 次，第二个 for 循环执行了 n_2 次，所以它的时间复杂度是 _O(_n_2)。
为什么执行 _n_2 次，这个数学知识在初中就已经学过。

O(logn), O(nlogn)

对数阶时间复杂度非常常见，同时也是最难分析的一种时间复杂度。
代码如下：

int  i = 1;
 while (i <= n)  {
   i = i * 2;
 }

只要 i<=n 这个表达式成立，while 循环语句就会一直执行下去。
所以，只要我们计算出这行代码执行了多少次，就能知道整段代码的时间复杂度。
从代码中可以看出，变量 i 的值从1开始，每进入一次循环就乘以 2。当 i 大于 n 时，循环结束。
实际上，变量 i 的取值就是一个等比数列。如果把它们一个一个列出来，应该是这个样子：

所以，我们只要知道 x 的值是多少，就知道这行代码执行的次数了。通过 2x=n 求解这个问题在高中数学就学过了。
x=log_2_n ，所以，这段代码的时间复杂度就是 O(log_2_n)。
把代码稍微改一下，下面这段代码时间复杂度是多少：

i=1;
 while (i <= n)  {
   i = i * 3;
 }

根据刚刚的解题思路，这段代码的时间复杂度是 O(log_3_n)。
如果一段代码的时间复杂度是 O(logn)，我们循环执行n遍，时间复杂度就是 O(nlogn)。
O(nlogn) 是一种非常常见的算法时间复杂度。比如，归并排序、快速排序的时间复杂度都是 O(nlogn)。