本文共 530 字，大约阅读时间需要 1 分钟。

运行时间计算

大O运行时间

 大O运行时间是上界

一般准则

●for循环：

if()	S1else	S2

 不超过判断+S1和S2运行时间长者的总的运行时间

递归

●情况一：实质上是for循环，所以为O(N)

int fun(int n){   	if(n <= 1)		return 1;	else		return n * fun(n - 1);}

●情况二：难以转为循环结构

int fun(int x){   	if(x <= 1)		return 1;	return fun(x-1) + fun(x-2);}

 假设运行时间为T(N)，则T(N) = T(N - 1) + T(N - 2) + 2，而Fib(N) = Fib(N - 1) + Fib(N - 2)，Fib以指数速度增长，所以T(N)也以指数增长，这是最坏的情况。因为该程序做了大量的多余工作。

对数运行时间

 如果一个算法以常数时间将问题的大小削减为其一部分（通常为1/2），那么该算法就是O(logN)。如二分查找