算法的时间复杂度和空间复杂度

素颜马尾好姑娘i 2021-10-01 04:58 378阅读 0赞

### 算法的时间复杂度和空间复杂度 ###

*   *  1）如何衡量一个算法的优劣
     *  2）相关定义：
     *  3）常见的时间复杂度
     *  4）计算时间复杂度的方法
     *  5）平均时间复杂度和最坏时间复杂度
     *  6）案例-->语句频度

## 1）如何衡量一个算法的优劣 ##

*  时间复杂度
 *  空间复杂度

## 2）相关定义： ##

- 语句频度：一个算法中语句执行的次数称为语句频度，记为T(n)。
     - 时间复杂度：一般情况下，算法中的基本操作语句的重复执行次数是问题规模n的某个函数用T(n)表示。若有某个辅助函数f(n)，使得当n趋近于无穷大时，T(n)/f(n)的极限为不等于零的常数。则称f(n)是T(n)的同数量级函数。记作：T(n)=O(f(n))。称O(f(n))为算法的渐进时间复杂度，简称：时间复杂度。T(n)不同，但时间复杂度可能相同。如：T(n)=n^2+5n+6  与 T(n)=3n^2 +3n+2，他们的T(n)不同但时间复杂度相同都为T(n^2)。
     - 空间复杂度 ：算法在执行过程中所涉及消耗的内存空间，另外算法的空间复杂度算的是变量的个数，有没有开辟辅助空间。

## 3）常见的时间复杂度 ##

- 常数阶O(1)
     - 对数阶O(log2n)
     - 线数阶O(n)
     - 线性对数阶O(nlog2n)
     - 平方阶O(n^2)
     - 立方阶O(n^3)
     - k方阶O(n^k)
     - 指数阶O(2^n)

## 4）计算时间复杂度的方法 ##

- 用常数1代替运行时间中所有加法常数项
     - 修改后的运行次数函数中，只保留最高阶
     - 去除最高阶项的系数

## 5）平均时间复杂度和最坏时间复杂度 ##

- 平均时间复杂度：是指所有可能的输入实例均已等概率出现的情况下，该算法的运行时间。
     - 最坏情况下的时间复杂度：称为最坏时间复杂度。一般讨论的时间复杂度均是最坏情况下的时间复杂度。这样做的原因是：最坏情况下的时间复杂度是算法在任何输入实例上运行时间的界限这就保证了算法的运行时间不会比最坏情况更长。

## 6）案例–>语句频度 ##

public class testDemo {
    	//100以内的所有数之和
    	public static void main(String[] args) {
    		int total = 0;
    		int end = 100;
    		//方法一：语句频度 T(n) = n + 1
    		for(int i = 0;i <= end; i++) {
    			total += i;
    		}
    		System.out.println("方法一："+total);
    		
    		//方法二：语句频度 T(n) = 1
    		total = (1+end)*end/2;
    		System.out.println("方法二："+total);
    	}
    }