时间复杂度和空间复杂度
算法
算法是指的解决特定问题求解所用的步骤，具有以下特点：
- 输入：算法需要具有零个或者多个输入。
- 输出：有一个或者多个输出。
- 有穷性：算法在执行有线的步骤后，自动结束不会出现无限循环的情况，并且每一个步骤都在可接受的时间内完成。
- 确定性：算法的每一步都必须含义明确，不能模棱两可出现不确定性。
- 可行性：算法的每一步都必须可行，不能出现无法运行的情况。
以上主要是算法的一些特点，从这些特点可以感觉出来，算法有点像是我们日常所写出的程序，比如：
int a =5;
int b = 4;
int c = a + b;
for(int i = 0;i < 10;i ++)
int arr[i] = i;上述的给a，b赋值，求a、b的和以及for循环都是算法。
计算机可以执行的基本算法包括以下四类：
1. 算术运算：加减乘除运算
2. 逻辑运算：且、或、非等运算
3. 关系运算：大于、小于、不等于和等于等运算
4. 数据传输：输入、输出、赋值等运算
算法的选择
我们都知道同一个问题有不同的算法解决，那么这些算法之间有许多的不同，比如运行时间，运行占用内存，代码易读性等方面。那么每个算法有这么多的不同，我们选择解决方案时只能选择一种，这个时候判断我们要选择哪个算法的依据是什么呢？
在这里我们引入了时间复杂度和空间复杂度这两个概念来作为选择适合算法的两条重要依据，一般对比算法的好坏基本从它的时间复杂度和空间复杂度这两个方面来综合判断就可以得出哪个更加适合。复杂度通常来说越小越好。
一个算法语句总的执行次数是关于问题规模N的某个函数，记为f(N)，N称为问题的规模。语句总的执行次数记为T(N)，当N不断变化时，T(N)也在变化，算法执行次数的增长速率和f(N)的增长速率相同。则有T(N) =
O(f(N))，称O(f(n))为时间复杂度的O渐进表示法
时间复杂度
时间复杂度是一个函数，定性描述了一个算法的运行时间。时间复杂度同通常用大O符号表述，可以简单理解为这个算法当中基本操作运行的次数 。在计算的时候使用了一种数学上求极限的思想。下面我们来看关于空间复杂度的计算。
时间复杂度的计算
a. 在一个循环中，循环次数即为其时间复杂度，如：
void Test0(int n)
{
int iCount = 0;
for (int iIdx = 0; iIdx < 10; ++iIdx)
{
iCount++;
}
}这个算法中，总执行次数为iCount和iIdx的赋值各一次，加上for循环的循环次数10次，共计12次。
b.一个算法中包含两个或者多个独立循环时，总时间复杂度为各个循环次数之和。
c.当循环存在包含关系时，执行次数为这两个循环的循环次数乘积。
一般算法O（n）的计算方法
用常数1取代运行时间中的所有加法常数
在修改后的运行次数函数中，只保留最高阶项
如果最高阶项系数存在且不是1，则去除与这个项相乘的常数
特殊时间复杂度
1.二分查找
因为每次的计算，都可以把查找的范围缩小一半，所以二分查找的时间复杂度为O（log2 N)。
2.斐波那契的递归算法
因为每次的展开都要把当前的已知项再拆分成当前数目的两倍，所以斐波那契的递归算法时间复杂度为2^N。
斐波那契的时间复杂度算法如上图所示，计算n第N个斐波那契数的大小时，共需计算2^N - 1次。
空间复杂度
一个程序的空间复杂度是指运行完一个程序所需内存的大小。利用程序的空间复杂度，可以对程序的运行所需要的内存多少有个预先估计。一个程序执行时除了需要存储空间和存储本身所使用的指令、常数、变量和输入数据外，还需要一些对数据进行操作的工作单元和存储一些为现实计算所需信息的辅助空间。程序执行时所需存储空间包括以下两部分。
（1）固定部分。这部分空间的大小与输入/输出的数据的个数多少、数值无关。主要包括指令空间（即代码空间）、数据空间（常量、简单变量）等所占的空间。这部分属于静态空间。
（2）可变空间，这部分空间的主要包括动态分配的空间，以及递归栈所需的空间等。这部分的空间大小与算法有关。
一个算法所需的存储空间用f(n)表示。S(n)=O(f(n)) 其中n为问题的规模，S(n)表示空间复杂度。
特殊空间复杂度
在斐波那契数求空间复杂度的过程中，我们需要考虑函数栈帧的过程，比如当我们求第五个斐波那契数的时候，这时候需要先开辟空间存放第四个数，然后再开辟空间存放第三个数，当开辟空间到第二个和第一个数的时候，第三个数得到结果并返回到第四个数中，第四个数的值已知后返回到第五个数中，在这个过程中，最大占用空间即为层数减一。如下图：
开辟空间的大小最多等于层数+1，也就是说求第N个斐波那契数，空间复杂度即为O（N）。
二分查找因为整个运算过程没有空间的改变，所以空间复杂度为O（1）。