算法的时间复杂度和空间复杂度（一）
——算法复杂度之时间复杂度
一、 前言 算法效率
如何衡量一个算法的好坏？ 让我们来看一下斐波那契数列：
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的渐进表示法，去掉那些对结果影响不大的项，结果也与原来的也大差不差，简洁明了的表示出了执行次数。**！本质计算的是属于哪个量级 **
！注意：在实际中一般情况关注的是算法的最坏运行情况
后续还会继续更新下半部分《算法复杂度（二）之空间复杂度》，若更新出会把博客文章的链接放在这里，
也会更新对于时间复杂度例题的讲解，引入更深入的思考与体会，敬请关注。
