下面代码就表示是\(O(logn)\)
while (left <= right) { int mid = (left - right) / 2 + right; if (target == nums[mid]) { return mid; } else if (target > nums[mid]) { left = mid + 1; } else { right = mid - 1; } } 4.函数调用main方法调用外部方法，两个方法都是一层循环，则\(O(n^2)\)
int main(int argc, char *argv[]) { for(int i=0;i<n;i++){ fun(n); } } void fun(int count){ for(int i=0;i<count;i++){ printf(); } }常见时间复杂度的比较：
\(O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)...<O(n!)<O(nn)\)
4. 时间复杂度的计算 1.计算规则1） 加法规则
\(T(n,m) = T1(n) + T2(n) = O ( max (f(n), g(m) ) \)
2) 乘法规则
\(T(n,m) = T1(n) * T2(m) = O (f(n) * g(m)) \)
\(O(n)*O(m)=O(n*m)\)
3)一个特例
在大O表示法里面有\(T(n) = T1(n) * T2(n) = O ( c*f(n) ) = O( f(n) )\). 一个特例，如果\(T1(n) ＝ O(cf(n))\)， c是一个与n无关的任意常数，$T2(n) = O ( f(n) ) $则有
总结：
1.用常数1取代所有的加法常数 t(n)=5 O(1)
修改后的函数中，只保留最高阶数
3.如果最高阶数的常数部分存在不是1，变成1。
比如：
\(T(n) = n^3 + n^2 + 29，此时时间复杂度为 O(n^3)。 T(n) = 3n^3，此时时间复杂度为 O(n^3)\)。
在算法分析中，主定理（英语：master theorem）提供了用渐近符号（大O符号）表示许多由分治法得到的递推关系式的方法。这种方法最初由Jon Bentlery，Dorothea Haken和James B. Saxe在1980年提出，在那里被描述为解决这种递推的“天下无敌法”(master method)。此方法经由经典算法教科书Cormen，Leiserson，Rivest和Stein的《算法导论》 (introduction to algorithm) 推广而为人熟知
解释： 上面的主定理就是根据递归式，我们需要找到它的时间复杂度，这里为了不区别其他的表示法，全部记为大O表示法，
例子1:
假设问题规模为N，某一个递归算法的时间程度记T(N)，已知T(1) = 0,T(N) = T(N/2) + N,求用O表示该算法的时间复杂度？
分析：直接套用公式可知，a = 1， b = 2 ,f(n) = N , 主定理主要和\(n^{\log_b a}\)做比较，带入可得 \(n^{\log_b a}= 1\) 。
所以f（n）> \(n^{\log_b a}\) ,符合条件三，所以T（n） = O(n)。
例子2:
假设问题规模为N，某一个递归算法的时间程度记T(N)，已知T(1) = 0,T(N) = 2T(N/2) + N/2,求用O表示该算法的时间复杂度？
分析：直接套用公式可知，a = 2， b = 2 ,f(n) = N/2 , 主定理主要和\(n^{\log_b a}\)做比较，带入可得 \(n^{\log_b a}= n\) 。
这里需要注意，f（n）和\(n^{\log_b a}\)做比较 ，比较的是它们的渐近增长率，所以f（n）= \(n^{\log_b a}\) ,符合条件二，都是一次函数，所以T（n） = O(nlogn)。
例子3:
求下面代码的时间复杂度：
void Hanoi(int n, char a, char b, char c)//a为原始柱，b为借助柱,c为目标柱 { if (n == 1) { Move(a, c);//只有一个盘子时直接移 } else { Hanoi(n - 1, a, c, b);//将A柱子上n-1个盘子借助C柱子移到B上 Move(a, c);//将A最后一个盘子移到C上 Hanoi(n - 1, b, a, c);//将B柱子借助空A柱子移到C上 } }分析：我们可以看出，用递归来解决汉诺塔问题是非常方便的选择，最后我们来分析一下汉诺塔问题的时间复杂度。
设盘子个数为n时，需要T（n)步，把A柱子n-1个盘子移到B柱子，需要T（n-1)步，A柱子最后一个盘子移到C柱子一步，B柱子上n-1个盘子移到C柱子上T（n-1)步。 得递推公式T（n）=2T（n-1)+1 。这个递推式子不符合主定理，所以需要运用高中的基础数学知识，
由递推式可以知道，凑方法，凑成等比数列，凑成通项公式 \(O（2^n）\)
例子4:
假设问题规模为N，某一个递归算法的时间程度记T(N)，已知T(1) = 0,T(N) = T(N- 1) + N,求用O表示该算法的时间复杂度？
分析：首先要看主定理的限定的条件，b > 1 才可以执行这个主定理，这里需要\(T(N) = T(N- 1) + N 变成 T(N) - T(N- 1) = N。 可以T（1） ，T（2） .... T(N) 叠加后可以算出T（N）的通项公式。 可以计算O（n^2）\)
三、空间复杂度类比于时间复杂度的讨论，一个算法的空间复杂度是指该算法所耗费的存储空间，计算公式计作：S(n) = O(f(n))。其中 n 也为数据的规模，f(n) 在这里指的是 n 所占存储空间的函数。一般情况下，我们的程序在机器上运行时，刨去需要存储程序本身的输入数据等之外，还需要存储对数据操作的「存储单元」。如果输入数据所占空间和算法无关，只取决于问题本身，那么只需要分析算法在实现过程中所占的「辅助单元」即可。如果所需的辅助单元是个常数，那么空间复杂度就是 O(1)。