大话数据结构开篇：时间复杂度和空间复杂度

1. 算法的复杂度：

算法的复杂度分为时间复杂度和空间复杂度，时间复杂度是指衡量算法执行时间的长短；空间复杂度是指衡量算法所需存储空间的大小。

2. 时间复杂度：
2.1 时间频度：一个算法中语句执行次数称为时间频度，计为T(n)。

2.2 时间复杂度：算法的时间复杂度描述的是T(n)的变化规律，计作：T(n) = O(f(n))。

用大写O( )来体现算法复杂度的记法称为大O记法，一般情况下随着n的增大，T(n)增长最慢的算法为最优算法。

时间频度不同，但时间复杂度可能相同。如：T(n)=n_²+3n+4与T(n)=4n²+2n+1它们的频度不同，但时间复杂度相同，都为O(n²)。

2.3 推导大O阶：

（1）用常数1取代运行时间中的所有加法常数，如O(1)。

（2）在修改后的运行次数函数中，只保留最高阶数，如n²+n 为 O(n²)。

（3）如果最高阶数存在且不是1，则去除与这个项相乘的常数，如3n³ 为 O(n³)。

2.4 常见时间复杂度：

【1】常数阶：

/*
 * 这个算法的运行次数是f(n)=3,与n的大小无关
 * 根据推导大O阶的方法,常数项3改为1,即时间复杂度为O(1)
 * 对于分支结构(不含循环结构),无论真或假,执行的次数都是恒定的
 * 不会随着n的变大而发生变化,其时间复杂度也是O(1)
 */
int sum = 0, n = 100; // 执行一次
sum = (1 + n) * n / 2; // 执行一次
System.out.println(sum); // 执行一次

【2】 线性阶：

/* 时间复杂度为O(n),因为循环体中的代码要执行n次*/
for(int i = 0; i < n; i++){
	;
}

【3】对数阶：

/*
 * 每次count乘以2之后,就距离n更近了一分
 * 有x个2相乘后大于n就会退出循环
 * 由2的x次方等于n --> x = logn,时间复杂度为O(logn)
 */
int count = 1;
while(count < n){
	count = count * 2;
}

【4】 平方阶：

/*
 * 对应外层循环,不过是内部这个时间复杂度为O(n)的语句,在循环n次
 * 所以这段代码的时间复杂度为O(n²)
 */
for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++){
		;
	}
}

【5】对比图：

常用时间复杂度所耗费时间从小到大依次为：O(1) < O(logn) < O(n) < O(nlogn) < O(n²) < O(n³) < O(2ⁿ) < O(n!) < O(nⁿ)

2.5 最坏时间复杂度：

最坏情况下的时间复杂度称最坏时间复杂度。一般不特别说明，讨论的时间复杂度均是最坏情况下的时间复杂度。 这样做的原因是：最坏情况下的时间复杂度是算法在任何输入实例上运行时间的上界，这就保证了算法的运行时间不会比任何更长。

3. 空间复杂度：
算法的空间复杂度通过计算算法所需的存储空间实现，算法的空间复杂度的计算公式为： S(n) = O(f(n))。

通常没有特别指明时，复杂度指的是时间复杂度，我们写代码时，要学会以空间来换取时间。