DataStructure_2.Algorithm

本文主要是介绍DataStructure_2.Algorithm，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

2.1 算法(是解决特定问题求解步骤的描述)在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作。

2.2 算法五个基本特征{输入，输出，有穷性，确定性，可行性}

2.2.1 输入输出：算法至少有0个输入，必须有输出。

2.2.2 有穷性：算法在执行有限的步骤后，自动结束而不会出现死循环，且每一个步骤在可接受的时间内完成。

2.2.3 确定性：算法的每一个步骤都有确定的意义，不会出现二义性，即无歧义，相同的输入只会得出唯一的输出结果。

2.2.4 可行性：算法的每一步必须是可行的，都能通过执行有限次数完成，即意味着可以被转换为程序并上机运行。

2.3 算法的设计{正确性，可读性，健壮性，时间效率高和存储量低}

2.3.1 健壮性：当输入数据不合法的时候算法也能做出相关处理，而不是产生异常或莫名其妙的结果。

2.3.2 时间效率高和存储量低：花最短的时间最少的钱办最大的事。

2.4 算法效率的度量方法{事后统计，事前分析估算}

2.4.1 事后统计方法：通过设计好的测试程序和数据，利用计算机计时器对不同算法编制的程序的运行时间进行比较，以确定

效率高低。但是，受①硬件性能②程序必须先编好③测试数据设计困难影响，导致这种方法有很大缺陷。

2.4.2 事前分析估算方法：依据统计方法在程序编写前对算法进行估算。测定运行时间最可靠的方法就是对运行的时间有消耗

的基本操作的执行次数。运行时间与这个执行次数成正比。

例：求1+2+…+100的值

算法1

int i,sum=0,n=100; //执行1次

for(i=1;i<=n;i++){ //执行n+1次

sum=sum+i; //执行n次

}

cout<<sum; //执行1次

/*共执行2n+3次*/

算法2

int sum=0,n=100; //执行1次

sum=(1+n)*n/2; //执行1次

cout<<sum; //执行1次

/*共执行3次*/

2.5 函数的渐进增长

2.6 算法时间复杂度

算法的时间复杂度，也就是算法的时间量度，记作：T(n)=O(f(n))。它表示随问题规模n的增大，算法执行时间的增长率和f(n）的增长率相同，称作算法的渐近时间复杂度，简称为时间复杂度。其中f(n）是问题规模n的某个函数。

这样用大写O( )来体现算法时间复杂度的记法，我们称之为大O记法。

一般情况下，随着n的增大，T(n)增长最慢的算法为最优算法。
推导大O阶方法
- 用常数1取代运行时间中的所有加法常数。

int sum=0,n=100; //执行1次

sum=(1+n)*n/2; //执行1次

cout<<sum; //执行1次

/*共执行3次*/

step1:运行次数函数为f(n)=3,故用常数1取代3。

step2:只保留最高阶项，而由于它没有最高阶项，故时间复杂度为O(1)

注：单纯不包含在循环结构中的分支结构(if else switch)时间复杂度也是O(1)

level two 对数级

例如while(count < n){count = count *3；//O(1)时间复杂度}

count每次3倍，x次后大于n，即3^x = n，即x=log3n，故循环的时间复杂度为O(logn)
level three 线性级

关键是分析循环结构运行情况

例如for(i=0;i<n;i++){cout<<"test!"；//O(1)时间复杂度}

函数体中的O(1)时间复杂度的代码一共要执行n次，故时间复杂度为O(n)
level four 平方级

嵌套循环
- 例1 两个O(n)的循环嵌套
  
  for(i=0;i<n;i++){
  
  for(j=0;j<n;j++){
  
  cout<<"test!"；//O(1)时间复杂度
  
  }
  
  } //时间复杂度为O(n^2=n*n)
- 例2 O(m),O(n)嵌套
  
  for(i=0;i<m;i++){
  
  for(j=0;j<n;j++){
  
  cout<<"test!"；//O(1)时间复杂度
  
  }
  
  } //时间复杂度为O(n*m)
- 例3 相互嵌套
  
  for(i=0;i<n;i++){
  
  for(j=i;j<n;j++){
  
  cout<<"test!"；//O(1)时间复杂度
  
  }
  
  }