算法的时间复杂度和空间复杂度(一)
——算法复杂度之时间复杂度
一、 前言 算法效率
如何衡量一个算法的好坏? 让我们来看一下斐波那契数列:
long long Fib(int N) { if (N < 3) return 1; return Fib(N - 1) + Fib(N - 2); }
斐波那契数列的递归实现方式看上去非常简洁吧 ,但简洁就代表效率高了吗?
下面就让我们来探讨一下到底怎样才是效率高
二、算法的复杂度
算法的复杂度一般取决于两个维度:时间维度,空间维度。
- 时间复杂度:衡量算法的运行快慢 运行所需时间
- 空间复杂度:衡量算法运行所需开辟的额外空间
在计算机发展的早期 ,计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展,计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复杂度。
2.1 时间复杂度
时间复杂度的定义:在计算机科学中,算法的时间复杂度是一个函数,它定量描述了该算法的运行时间。
一个算法执行所耗费的时间,从理论上说,是不能算出来的,只有你把你的程序放在机器上跑起来,才能知道。但是我们需要每个算法都上机测试吗?是可以都上机测试,但是这很麻烦,所以才有了时间复杂度这个分析方式。一个算法所花费的时间与其中语句的执行次数成正比例,算法中的基本操作的执行次数,为算法的时间复杂度
[即:找到某条基本语句与向题规模之间的数学表达式、就是算出了该算法的时间复杂度]
脱离实际的运行环境和硬件环境的情况下,比较其性能,才能真正评出算法效率优劣。
\\计算一下下列函数中++count语句总共执行了多少次 void Func1(int N) { int count = 0; for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) { ++count; } } for (int k = 0; k < 2 * N; ++k) { ++count; } int M = 10; while (M--) { ++count; } printf("%d", count); }
Func1执行的基本操作次数:
F ( N ) = N 2 + 2 ∗ N + 10 F(N)=N^2+2*N+10F(N)=N2+2∗N+10
- N=10 F(N)=130
- N=100 F(N)=10210
- N=1000 F(N)=1002010
实际我们我们计算时间复杂度时,并不一定要计算精确的执行次数
不知大家是否还记得上初中的一道非常经典的数学题
( n − 1 ) / n (n-1) / n(n−1)/n
n — > ∞ n—>∞n—>∞
结果会是多少呢
当n接近于无穷大时,1与之相比相差悬殊,可以忽略不计了
≈ n / n = 1 ≈n /n =1≈n/n=1
还有高中时期的一道经典数学题
关于小数点
0.31415926....... 0.31415926.......0.31415926.......
真正起决定作用的只有前几位,而后面那几位0.00000…太小了,完全可以忽略不记了
所以只需要计算出真正对大小起决定性作用的部分,大概执行次数,因此就有了 " 大O的渐进表示法 "
三、大O的渐进表示法 : 抓大头(取起决定性作用的部分)
大O符号(Big O notation):是用于描述函数渐近行为的数学符号
推导大O阶方法
理解:
- 用常数1取代运行时间中的所有加法常数
O(1)不是代表只执行了1次,而是代表常数次
(cpu处理1万亿的数值,和处理数值1 的时间一样快)
- 用修改后的运行次数函数中,只保留最高阶项
- 如果最高阶项存在且不是1,则去除与这个项目相乘的常数
相乘的常数与次方相比 可省略
得到的结果就是大O阶。
★☆★推导大O阶方法与经验总结:
- 常数都当成1,只保留最高阶项,最高阶的系数去掉
- 有循环算循环,没有循环当常数即可
通过大O渐进表示法,我们前面的例题Func1的时间复杂度为:
O ( N 2 ) O(N^2)O(N2)
- N=10 F(N)=100
- N=100 F(N)=10000
- N=1000 F(N)=1000000
使用大O的渐进表示法,去掉那些对结果影响不大的项,结果也与原来的也大差不差,简洁明了的表示出了执行次数。**!本质计算的是属于哪个量级 **
!注意:在实际中一般情况关注的是算法的最坏运行情况
后续还会继续更新下半部分《算法复杂度(二)之空间复杂度》,若更新出会把博客文章的链接放在这里,
也会更新对于时间复杂度例题的讲解,引入更深入的思考与体会,敬请关注。