icql

算法_概述

一、定义

算法:是解决问题求解步骤的描述

二、算法的复杂度分析

1) 大O复杂度表示法

渐进表示法:随入参增大的趋势分析

分析原则:

>只关注循环执行次数最多的一段代码
>加法法则:总复杂度等于量级最大的那段代码的复杂度
>乘法法则:嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

常见复杂度:

(1)单参数:
O(1)常数阶 < O(logn)对数阶 > < O(n)线性阶 < O(nlogn)线性对数阶 < O(n^2)平方阶 < O(n^3)立方阶 < O(2^n)指数阶

(2)多参数:
O(m+n) < O(m*n)

2) 时间复杂度分析

时间耗费与输入n的关系(用大O法表示渐进时间复杂度)

>最好情况时间复杂度
>最坏情况时间复杂度
>平均情况时间复杂度
>均摊时间复杂度

3) 空间复杂度分析

内存占用与输入n的关系(用大O法表示渐进空间复杂度)

4) 常见示例

//1、常数阶,f(n) = 3,O(3) => O(1)
int sum = 0, n = 0;//执行 1 次
sum = (1 + n) * n / 2;//执行 1 次
System.out.println(sum);//执行 1 次

//2、线性阶,f(n) = c*n,O(c*n) => O(n)
for (int i = 0; i < n; i++) {
	//O(1)的语句;
}

//3、对数阶,10^f(n) = n,f(n) = lgn,O(lgn)
int count = 1;
while (count < n) {
	count = count * 10;
	//O(1)语句;
}

//4、平方阶,f(n) = n*n,O(n^2)
for (int i = 0; i < n; i++) {
	for (int j = 0; j < n; j++) {
		//O(1)语句;
	}
}