时间复杂度
时间复杂度估算方法
1.简单语句
简单的赋值语句，读写语句，可以看作所用时间为常量记为O(1)。
2.分支语句
在分支语句中，以所耗费时间最多的那个分支来计算时间复杂度。
3.循环语句
在循环语句中，每循环1次记为O(1)，循环n次时间复杂度为O(n)。
4.嵌套循环
在嵌套循环中，时间复杂度是多个循环的叠加，如下所示：
| for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) ……. | O(n*n)=O()
|
| for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) for(int k=1;k<=n;i++) ……. | O(n*n)=O() |
| for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ ….. } for(int k=1;k<=n;i++){ ……. } } | O(n*n)=O(2*)
|
空间复杂度
编写的程序运行时的代码和数据等信息，保存在我们的内存中，我们的内存到底能装多少数据，这个与计算机内存大小，运行其它程序的多少有关。一般来讲全局数据内存大可达到（亿级个整数），局部变量内存较少可达到（千万级个整数）。例如下程序：
| int a[100000000] int dis(){ int b[10000000]; } | //全局变量数组 //局部变量数组 |
程序运行将计算机内存分为如下四个区域：
1.程序代码区：运行程序本身所需要的存储空间，它与程序规模大小有关，一旦程序运行，不能进行动态管理，除非进程杀掉它。
2.全局数据区：用以存放全局变量、静态变量和常量的地方，生命周期与程序一致，即程序运行它就会占用空间，直到程序结束。
3.栈区：存放局部变量和形参变量的地方，在函数调用时自动分配，调用完毕后会自动释放，包括主函数。
4.堆区：动态分配的指针变量，这需要开发人员手动申请和手动释放。
函数调用机制
- 主调函数调用被调函数
- 主动权给被调函数
- 为形参和局部变量分配内存
- 实参与形参匹配传值
- 被调函数返回主调函数
- 主动权返回主调函数
- 计算结果返回
- 释放形参和局部变量内存空间
- 四种交换函数
下面四个交换函数，在函数进行调用用以实现数据交换，其结果为：
| void swap1(int a,int b){ int c=a; a=b,b=c; } | 不能实现主函数数据交换： 在被调函数内实现了交换，但在函数调用结束后被释放了。 |
| void swap2(int &a,int &b){ int c=a; a=b,b=c; } | 能实现交换，将主函数的变量作为副本传入，形参与实参是统一个地址。 |
| void swap3(int *a,int *b){ int *c=a; a=b,b=c; } | 不能，函数内实现了指针的交换，而指针所指向地址的值没变，而a,b,c释放并没影响原有地址内容。 |
| void swap4(int *a,int *b){ int c=*a; *a=*b,*b=c; } | 能实现交换，实现的是指针所指向地址的值进行了交换。 |
算法设计的步骤：
1、认真读取题目，理解含义，注意细节。
2、根据题目初步确定算法。
3、根据初步算法，进行数据结构的设计。
4、查看数据规模，衡量算法的时间复杂度和空间复杂度，从而确定初步算法是否可行，若不行，从新确定算法。
5、编程实现代码。
6、进行测试，注意边界条件，（数据类型等）。
