目录
引：
·问：程序是什么?
·答：程序=算法+数据结构。
????????综上所述，程序主要由算法与数据结构组成。那何为算法，何为数据结构呢？
????????算法，就是定义良好的计算过程，它取一个或一组的值为输入，并通过计算产生出一个或一组值作为输出。简单来说，算法就是一系列的计算步骤，用来将输入数据转化为输出结果。
? ? ? ? 而数据结构，是计算机存储、组织数据的方式，指相互之间存在一种或多种特定关系的数据元素的集合。
????????了解完算法与数据结构的定义，那么咱们开始进一步学习。比起实际应用的程序，初识C语言篇中的代码不过星与皓月之别。不过也恭喜你，学完C语言，你成功拿到了正式学习编程的门票！此，祝你好运！
一、时间复杂度与空间复杂度
1.算法效率
????????算法效率分析分为两类：一为时间效率，二为空间效率。
????????时间效率为时间复杂度，主要衡量一个算法的运行速度；而空间效率即空间复杂度，主要衡量一个算法所需存储空间的量度。当然，随着近年来计算机的快速发展，计算机的存储空间已经达到了很高的程度，所以在一定程度上，空间复杂度不再需要特别关注。
? ? ? ? 接下来讲解两种复杂度主要就通过各个实例来让大家认识了解不同类型的复杂度的计算。
补：
? ? ? ? 算法必须满足的五大重要特性-有穷性、确定性、可行性、输入、输出。
? ? ? ? 算法优劣的评判标准-正确性、可读性、健壮性（完善性）、高效性。
2.时间复杂度
2.1 时间复杂度的概念
????????时间复杂度的定义：一个算法所花费的时间与其中语句的执行次数成正比例，算法中的基本操作的执行次数,就为算法的时间复杂度。
说明：
? ? ? ? 在计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。而一个算法执行所需要的时间，在理论上说，是不能算出来的，只有当程序在计算机上运行时，才能知道，但由于计算机运行效率以及其他因素，所以采用时间复杂度这一分析方式来定量的描述算法执行所耗费的时间。
?2.2 时间复杂度的计算
代码1 _ 1，时间复杂度计算：
void Func(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\n",count);
} Func执行的基本操作次数：
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? f(n) = n^2 + 2*n + 10
时间复杂度的计算：
>>计算方法-大O的渐进表示法，即当问题规模充分大时，n趋于无穷，算法中基本语句的执行次数在渐进意义下的阶。
推导大O阶方法：1、用常数1取代运行时间中的所有加法常数。2、在修改后的运行次数函数中，只保留最高阶项。3、如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶。????????所以，对于上述程序的时间复杂度T(n) = O( f(n) ) = O(n^2).
接下来是几个例子。
例1 _ 1，时间复杂度计算1：
void Func1(int n)
{
int count = 0;
for (int k=0; k < 2*n; ++k)
{
++count;
}
int M = 10;
while(M--)
{
++count;
}
printf("%d\n", count);
}Func1执行的基本操作次数：
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? f( n ) = 2*n + 10
时间复杂度的计算1：
>>当执行次数中，最高阶项系数为C时，C>0，我们往往忽略掉常数C。
? ? ? ? 所以，例1_1的时间复杂度 T( n ) = O( f(n) ) = O（ n ).
例1 _ 2 ，时间复杂度的计算2：
void Func2(int n, int m)
{
int count = 0;
for (int k = 0; k < m; ++ k)
{
++count;
}
for (int k = 0; k < n ; ++ k)
{
++count;
}
printf("%d\n", count);
}Func2执行的基本操作次数：?
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? f( n ) = m + n
时间复杂度的计算2：
>>当出现两个参数均趋向于无穷大时，且未知两者大小，则两者相加。
????????所以，例1_2的时间复杂度 T( n ) = O( f(n) ) = O( n + m).
代码1 _? 3，时间复杂度的计算3：
void Func3(int N)
{
int count = 0;
for (int k = 0; k < 100; ++ k)
{
++count;
}
printf("%d\n", count);
}Func3执行的基本操作次数：?
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? f( n ) = 100
时间复杂度的计算3：
>>当程序问题规模较小时，可数有限规模，此时基本语句的执行次数为某个常数，即使这个常数再大，时间复杂度都是O( 1 )。
????????所以，例1_3的时间复杂度 T( n ) = O( 1 )，称为常量阶.
例1 _? 4，时间复杂度的计算4：
// 计算strchr的时间复杂度？(在一个n长度字符串中找一个字符)
const char * strchr ( const char * str, int character );执行的基本操作次数：?
????????????????????????????????最好情况：1次找到
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 最坏情况：n次找到
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 平均情况：n/2次找到
时间复杂度的计算4：
>>有些算法的时间复杂度存在最好、平均和最坏情况，在实际中一般情况关注的是算法的最坏运行情况。
? ? ? ? 所以，例1_4的时间复杂度 T( n ) = O ( n ).
例1 _? 5，时间复杂度的计算5：
// 计算BubbleSort的时间复杂度？（冒泡排序）
void BubbleSort(int* a, int n)
{
assert(a);
for (size_t end = n; end > 0; --end)
{
int exchange = 0;
for (size_t i = 1; i < end; ++i)
{
if (a[i-1] > a[i])
{
Swap(&a[i-1], &a[i]);
exchange = 1;
}
}
if (exchange == 0)
break;
}
}执行的基本操作次数：?
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? f( n ) = n-1 + n-2 + n-3 +...+ 1
? ? ? ? 所以，例1_5的时间复杂度 T( n ) = O ( n^2 ).
例 1 _? 6，时间复杂度的计算6：
// 计算BinarySearch的时间复杂度？（二分查找）
int BinarySearch(int* a, int n, int x)
{
assert(a);
int begin = 0;
int end = n-1;
while (begin < end)
{
int mid = begin + ((end-begin)>>1);
if (a[mid] < x)
begin = mid+1;
else if (a[mid] > x)
end = mid;
else
return mid;
}
return -1;
}执行的基本操作次数：?? ? ? ? ? ?
????????????????????????????????最好情况：1次找到
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 最坏情况：log (2)(n)次（假设找了x次，则过程中除以了x个2，故2^x=N）
例 1 _? 7，时间复杂度的计算7：
// 计算阶乘递归Factorial的时间复杂度？
long long Factorial(size_t n)
{
return n < 2 ? n : Factorial(n-1)*n;
}执行的基本操作次数：
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 递归算法的时间复杂度=递归次数*每次递归函数中的次数
时间复杂度的计算7：
????????每次递归函数中的次数为1；递归次数，从F(n)~F(1)，共n次。
? ? ? ? 所以，例1_7的时间复杂度 T( n )? = O( n ).
例1 _ 8，时间复杂度的计算8：
// 计算斐波那契递归Fibonacci的时间复杂度？
long long Fibonacci(size_t n)
{
return n < 2 ? n : Fibonacci(n-1)+Fibonacci(n-2);
}执行的基本操作次数：(如图1)
? ? ? ? ?则f( n ) = 2^0 + 2^1 + ... + 2^(n-1)
时间复杂度的计算8：
? ? ? ? 假设每一层都是满的时，容易得其时间复杂度T( n ) = O( 2^n )；而当其中有空缺时，所空缺位置的个数是有限可数的，计为常数C。有f( n ) = 2^n - 1 - C。
? ? ? ? 所以，例1_8的时间复杂度 T( n )? = O( 2^n ).
? ? ? ? 可知，例1_8代码的时间复杂度非常大，在实际中并无太大意义。这种情况下，必须要降低其时间复杂度，一种思路即将递归改为循环，可以自己实现一下，并计算时间复杂度。
?2.空间复杂度
2.1 空间复杂度的概念
????????空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度 。空间复杂度不是程序占用了多少 bytes的空间，因为这个也没太大意义，所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟实践 复杂度类似，也使用大O渐进表示法。
注：时间是积累的，空间不是积累的，是可以复用的。
2.2 空间复杂度的实例
例2 _ 1，时间复杂度的计算1：
// 计算BubbleSort的空间复杂度？
void BubbleSort(int* a, int n)
{
assert(a);
for (size_t end = n; end > 0; --end)
{
int exchange = 0;
for (size_t i = 1; i < end; ++i)
{
if (a[i-1] > a[i])
{
Swap(&a[i-1], &a[i]);
exchange = 1;
}
}
if (exchange == 0)
break;
}
}例2 _ 2，时间复杂度的计算2：
// 计算Fibonacci的空间复杂度？
long long* Fibonacci(size_t n)
{
if(n==0)
return NULL;
long long * fibArray =(long long *)malloc((n+1) * sizeof(long long));
fibArray[0] = 0;
fibArray[1] = 1;for (int i = 2; i <= n ; ++i)
{
fibArray[i ] = fibArray[ i - 1] + fibArray [i - 2];
}
return fibArray ;
}例2 _ 3，时间复杂度的计算3：
// 计算阶乘递归Factorial的空间复杂度？
long long Factorial(size_t N)
{
return N < 2 ? N : Factorial(N-1)*N;
}