算法时间复杂度及效率（二）-创新互联
今天我们来看下算法复杂度和效率的问题，在判断一个算法的效率时，操作数量中的常数项和其他次要项常常是可以忽略的，只需要关注最高阶项就能得出结论。那么我们如何用符号定性的判断算法的效率呢？算法的复杂度分为两部分：1、时间复杂度，即算法运行后对时间需求量的定性描述；2、空间复杂度，即算法运行后对空间需求量的定性描述。
创新互联公司专注于集美企业网站建设,成都响应式网站建设,成都商城网站开发。集美网站建设公司,为集美等地区提供建站服务。全流程按需网站建设，专业设计，全程项目跟踪，创新互联公司专业和态度为您提供的服务数据结构重点关注的是算法的效率问题，因此，我们后面会集中于讨论算法的时间复杂度；但其使用的方法完全可以用于空间复杂度的判断！我们经常在进行算法的时间复杂度用大O表示法来进行分析。下来对此种方法进行说明，算法效率严重依赖于操作（Operation）数量；操作数量的估算可以作为时间复杂度的估算；在判断时首先关注操作数量的最高次项。如下：
下来我们来分析下常见的时间复杂度：
1、线性阶时间复杂度：O(n)。如下：
2、对数阶时间复杂度：O(logn)。如下
3、平方阶时间复杂度：O(n²)。如下：
下来我们来看看常见的时间复杂度，如下图所示
常见的时间复杂度的比较，如下
下面我们通过实例来进行分析下，下面的函数程序复杂度是怎样的
int find(int a[], int n, int v)
{
int ret = -1;
for(int i=0; i<=n; i++)
{
if( a[i] == v )
{
ret = i;
break;
}
}
return ret;
}我们如果定义的数组 a[5] = {1, 2, 3, 4, 5}； 如果是 int min = find(a, 5, 1)； 这种则是最好情况了，仅需执行 1 次循环，此时便是 O(1)；如果是 int max = find(a, 5, 5)；此时便是最坏的情况了，需要全部执行，此时便是 O(n)。那么此时算法的最好与最坏情况便体现出来了，当算法在最乖情况下仍然能满足需求时，可以推断，算法的最好情况和平均情况都满足需求。在以后没有进行特殊说明时，所分析算法的时间复杂度都是指最坏时间复杂度。
算法的空间复杂度（Space Complexity），其定义为 S(n) = S(f(n))。其中 n 为算法的问题规模，f(n) 为空间使用函数，与 n 相关。推倒时间复杂度的方法同样适用于空间复杂度，例如，当算法所需要的空间是常数时，其空间复杂度为 S(1)。我么来看看下面这个程序的空间复杂度为多少
long sum1(int n)
{
long ret = 0;
int* array = new int[n];
for(int i=0; i我们看到第一行为 1，第三行的 ret 定义也为 1，指针数组 array 的定义其空间复杂度为 n，下面两个进行 for 循环的空间复杂度分别为 1。因此整个程序所需的单位内存为： n + 4；即空间复杂度：S(n+4) = S(n)。那么时间跟空间之间是否存在某种联系呢？在多数情况下，算法的时间复杂度更令人关注，因为现在的内存都很大。如果有必要的话，可以通过增加额外空间降低时间复杂度；同理，也可以增加算法的耗时降低空间复杂度。下来我们来看个空间换时间的示例代码，代码的背景是在 1-1000 中的某些数字搜组成的数组中，设计一个算法类找出出现次数最多的数字。
#include
using namespace std;
void sreach(int a[], int len)
{
int pi[1000] = {0};
int max = 0;
for(int i=0; i我们来看看打印结果
我们看到打印了 3 和 6，因为大数 6 和 3 都出现了 3 次。那么此次我们的程序实现中函数的时间复杂度为 O(n)。那么问题来了，当两个算法的大 O 表示法相同时，是否意味着两个算法的效率完全相同呢？肯定是不相同的！通过今天对算法的时间复杂度和效率的学习，总结如下：1、时间复杂度是算法运行时对于时间的需求量；2、大 O 表示法用于描述算法的时间复杂度，它只关注操作数量的最高次项；3、常见的时间复杂度为：线性阶，平方阶和对数阶；4、一般而言，在工程中使用的算法其复杂度都不超过 O(n³)；5、算法分析与设计时，重点考虑最坏情况下的时间复杂度，大 O 表示法用于适用于算法的空间复杂度；6、空间换时间是工程开发中常用的策略。
本文名称：算法时间复杂度及效率（二）-创新互联
文章出自：http://6mz.cn/article/dhescg.html