什么是算法?
算法就是解决特定问题求解步骤的描述,在计算机中表现为指令的有限序列, 并且每个指令表示一个或多个操作.
算法的特性，一个算法应该具有以下五个特征：
1.有穷性（Finiteness）：算法的有穷性是指算法必须能在执行有限个步骤之后终止
2.确切性 (Definiteness): 算法的每一个步骤必须有确切的定义
3.输入项(Input)：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定出了初始条件
4.输出项(Output)：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的
5.可行性(Effectiveness)：算法中执行的任何计算步骤都是可以被分解为基本的可执行的操作步骤，即每个计算步骤都可以在有限时间内完成（也称之为有效性）
算法的设计要求：
1.时间复杂度
算法的时间复杂度是指执行算法所需要的计算工作量。一般来说，计算机算法是问题规模n 的函数f(n)，算法的时间复杂度也因此记做。
T(n)=Ο(f(n))
因此，问题的规模n 越大，算法执行的时间的增长率与f(n) 的增长率正相关，称作渐进时间复杂度（Asymptotic Time Complexity）。
2.空间复杂度
算法的空间复杂度是指算法需要消耗的内存空间。其计算和表示方法与时间复杂度类似，一般都用复杂度的渐近性来表示。同时间复杂度相比，空间复杂度的分析要简单得多。
3.正确性
算法的正确性是评价一个算法优劣的最重要的标准。
4.可读性
算法的可读性是指一个算法可供人们阅读的容易程度。
5.健壮性
健壮性是指一个算法对不合理数据输入的反应能力和处理能力，也称为容错性。
下面着重说一下算法的复杂度
算法复杂度分为时间复杂度和空间复杂度。其作用： 时间复杂度是指执行算法所需要的计算工作量；而空间复杂度是指执行这个算法所需要的内存空间。（算法的复杂性体运行该算法时的计算机所需资源的多少上，计算机资源最重要的是时间和空间（即寄存器（cpu的一部分））资源，因此复杂度分为时间和空间复杂度。）
在计算机科学中，时间复杂性，又称时间复杂度，算法的时间复杂度是一个函数，它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被称为是渐近的，亦即考察输入值大小趋近无穷时的情况。这个理解起来有些抽象，看下面的大O表示法以及具体实例
大O表示法主要有以下三种情况
1. 用常数1取代运行时间中所有常数 3->1 O(1)
2. 在修改运行次数函数中,只保留最高阶项 n^3+2n^2+5 -> O(n^3)
3. 如果在最高阶存在且不等于1,则去除这个项目相乘的常数 2n^3 -> n^3
常数阶时间复杂度计算 O(1)
//1+1+1 = 3 O(1)
void testSum1(int n){
int sum =0; //执行1次
sum = (1+n)*n/2; //执行1次
printf("testSum1:%d\n",sum);//执行1次
}
//1+1+1+1+1+1+1 = 7 O(1)
void testSum2(int n){
int sum =0; //执行1次
sum = (1+n)*n/2; //执行1次
sum = (1+n)*n/2; //执行1次
sum = (1+n)*n/2; //执行1次
sum = (1+n)*n/2; //执行1次
sum = (1+n)*n/2; //执行1次
printf("testSum2:%d\n",sum);//执行1次
}
//x=x+1; 执行1次 O(1)
void add(int x){
x = x+1;
}
线性阶时间复杂度
//x=x+1; 执行n次 O(n)
void add2(int x,int n){
for(inti =0; i < n; i++) {
x = x+1;
}
}
//1+(n+1)+n+1 = 3+2n -> O(n)
void testSum3(int n){
inti,sum =0; //执行1次
for(i =1; i <= n; i++) { //执行n+1次
sum += i; //执行n次
}
printf("testSum3:%d\n",sum); //执行1次
}
对数阶时间复杂度
//2的x次方等于n x = log2n ->O(logn)
void testA(int n){
int count =1; //执行1次
//n = 10
while(count < n) {
count = count *2;
}
}
平方阶
//x=x+1; 执行n*n次 ->O(n^2)
void add3(int x,int n){
for(int i =0; i< n; i++) {
for(int j =0; j < n ; j++) {
x=x+1;
}
}
}
//n+(n-1)+(n-2)+...+1 = n(n-1)/2 = n^2/2 + n/2 = O(n^2)
//sn = n(a1+an)/2
void testSum4(int n){
int sum =0;
for(inti =0; i < n;i++)
for(int j = i; j < n; j++) {
sum += j;
}
printf("textSum4:%d",sum);
}
//1+(n+1)+n(n+1)+n^2+n^2 = 2+3n^2+2n -> O(n^2)
void testSum5(int n){
int i,j,x=0,sum =0; //执行1次
for(i =1; i <= n; i++) { //执行n+1次
for(j =1; j <= n; j++) {//执行n(n+1)
x++; //执行n*n次
sum = sum + x; //执行n*n次
}
}
printf("testSum5:%d\n",sum);
}
立方阶
void testB(int n){
intsum =1; //执行1次
for(inti =0; i < n; i++) { //执行n次
for(intj =0; j < n; j++) { //执行n*n次
for(intk =0; k < n; k++) {//执行n*n*n次
sum = sum *2; //执行n*n*n次
}
}
}
}
空间复杂度
程序空间计算需要考虑的因素：
1.寄存本身的指令
2.常数
3.变量
4.输入
5.对数据进行操作的辅助空间
在考量算法的空间复杂度时，我们主要考虑算法执行时所需要的辅助空间，一般面试或者谈到求一个算法的空间复杂度一般都是指辅助空间的复杂度。
下面我们举个例子
数组逆序,将一维数组a中的n个数逆序存放在原数组中.
int main(int argc,const char* argv[]) {
// insert code here...
printf("Hello, World!\n");
int n =5;
int a[10] = {1,2,3,4,5,6,7,8,9,10};
//算法实现(1) - O(1)
int temp;//指用了一个临时变量，一个int 类型的辅助空间
//int a，b，c...//这样写空间复杂度也是O(1) 因为是常数阶
for(inti =0; i < n/2; i++){
temp = a[i];
a[i] = a[n-i-1];
a[n-i-1] = temp;
}
for(inti =0;i <10;i++)
{
printf("%d\n",a[i]);
}
//算法实现(2) O(n)
int b[10] = {0};//不是O(10)
for(int i =0; i < n;i++){ // 只用了n 个数据的空间
b[i] = a[n-i-1];
}
for(int i =0; i < n; i++){
a[i] = b[i];
}
for(int i =0;i <10;i++)
{
printf("%d\n",a[i]);
}
return 0;
}
git: https://github.com/HailongW/DataDtructureAndAogrithm.git
