北京中高端网站建设公司,怎样做电商,seo研究中心,帮人做网站一个多少钱前言 算法是解决问题的一系列操作的集合。著名的计算机科学家Niklaus Wirth曾提出#xff1a;算法数据结构程序#xff0c;由此可见算法在编程中的重要地位。本篇主要讨论算法性能好坏的标准之一——复杂度。 1 复杂度概述
1.1 什么是复杂度 本文所讨论的复杂度是指通过事先… 前言 算法是解决问题的一系列操作的集合。著名的计算机科学家Niklaus Wirth曾提出算法数据结构程序由此可见算法在编程中的重要地位。本篇主要讨论算法性能好坏的标准之一——复杂度。 1 复杂度概述
1.1 什么是复杂度 本文所讨论的复杂度是指通过事先估算法计算出的用来衡量算法效率的值。因此并不是说代码的长度越长复杂度就越高或者代码中的数据越多复杂度就越高。 1.2 为什么会有复杂度 关于复杂度的产生我们通过下图的问题来引入。假设现在有一个人要从A地前往E地那么他共有ABE、ADE、ABCE三种路径可以选择但是我们可以看出ABE的路程是最短的假设图中距离与实际距离成比例经过的地区也是最少的相较于其它两条路径ABE的优势非常明显。 算法是用来解决问题的操作步骤的集合而我们解决同一个问题可能会如上例一样有多种路径这时我们需要一个标准来评判每条路径的好坏。这样一来算法的复杂度就被提出了。 1.3 复杂度分类 算法的复杂度分为时间复杂度和空间复杂度两种。 时间复杂度用来衡量算法消耗时间的多少空间复杂度用来衡量算法所需开辟新空间的多少。 2 时间复杂度
2.1 什么是时间复杂度 首先我们要明白程序运行的绝对时间并不是衡量算法效率的标准。举个不太恰当的例子使用“ENIAC”计算机世界上第一台电子数字式计算机与“天河一号”超级计算机执行相同的算法死循环除外它们的绝对时间必然有所不同。 从中我们得出当我们评判一个算法的好坏时不能附带有硬件条件的影响而应关注算法本身。算法的执行时间的长度可以由每条语句的执行时间乘以该语句的执行次数再加和得到。而每条语句的单次执行时间对现代计算机来说几乎可以忽略不计那么对于一个程序的执行时间影响最大的因素就是单条语句的执行次数了。 因此时间复杂度主要是用来渐进表示执行次数最多的单条语句的执行次数。 2.2 时间复杂度的计算 时间复杂度通常用O表示。对于任意输入量n这里的输入量不一定是数字也可能为数组或结构变量等根据具体情况而定算法的时间复杂度可记作O(f(n))其中f(n)为n的函数表示算法中的语句的执行次数。但是我们通常会使用渐进表示法来表示时间复杂度即取f(n)中次数最高的项来表示当n足够大时最高次项对整个数值的影响最大。 如果仅仅通过这些文字来理解时间复杂度可能较为抽象我们通过几个简单的例子来理解一下。 int main()
{int a;int i;for(i0;i10;i)ai;return 0;
} 我们来看这段代码这其中代码执行的总次数即执行的语句数量为13为一个常数我们计这段代码的时间复杂度为O(1)。 这可能与大家的理解有些偏差明明执行次数为13为什么不计作O(13)呢我们来观察这段代码由于这段代码的输入量n对程序的运行次数不会产生影响那么无论输入量n的大小为多少这段代码的执行次数都是13。当输入量n趋向于无穷大时执行次数13与1的区别并不大可以忽略不计。为方便起见将这些执行次数为常数的算法的时间复杂度计为O(1)。 也就是说无论算法的语句执行次数为10,20,30还是一亿十亿一百亿只要它是常数那么当输入量n趋向于无穷大时这些常数均可忽略不计则时间复杂度计为O(1)。 int main()
{int a;int n;int i;scanf(%d,n);for(i0;in;i)ai;return 0;
} 我们再来看这段代码这段代码与之前的代码相比的不同之处在于其有一个输入量n并且输入量n会对代码的执行次数产生影响例如当输入2时代码执行次数为7输入量为10时代码执行次数为15。可以推出这段代码的执行次数与输入量n的关系为f(n)n5。 在这个关系中当n趋向于无穷大时5这个常量可忽略不计因此我们将这个算法的时间复杂度计为O(n)。 通过对上面两段代码的分析我们可以总结出一些规律对比可以发现影响时间复杂度的主要因素就是循环语句的循环次数与输入量n的关系。在第二段代码中输入量为n时循环语句执行n次则时间复杂度为O(n)。 int main()
{int i,j,n;scanf(%d,n);for(i0;in;i){for(j0;jn;j){printf(%d ,i*j);}}while(i--){j--;}return 0;
} 我们继续来看这段代码中存在嵌套循环语句当输入量为n时对于任意一次外层循环内层循环都进行n次。而外层循环也进行n次因此总共可认为进行n*n次即n^2。 除此之外这段代码中还存在另一段while循环语句不难得出循环进行n次因此这段代码执行的总次数可以计为n^2n2。当输入量n趋向于无穷大时相对于n^2n2的值对总次数的影响并不大可以忽略不计。 因此这段代码的时间复杂度计为O(n^2)。 2.3 一些经典算法的时间复杂度分析
2.3.1 冒泡排序 冒泡排序是一种简单的交换排序通过比较相邻两个元素的大小若它们的大小顺序与所需顺序不同则交换这两个元素。这里先不讨论冒泡排序的原理直接来分析代码。 void BubbleSort(int* a,int sz)
{int i,j;for(i0;isz-1;i) //排序次数{for(j0;jsz-i-1;j) //比较次数{if(arr[j]arr[j1]) //判断相邻两数据大小{int tmp arr[j];arr[j] arr[j1];arr[j1] tmp;}}}
} 上面为一段最简单的冒泡排序算法其中参数a为所需排序的数组的地址sz为所需排序的元素个数当给定数组大小为n时该算法的循环总共进行[(n-1)(n-2)...1]次化简可得(n^2-n)/2次因此该算法的时间复杂度计为O(n^2)。 2.3.2 二分查找 二分查找是一种非常高效的查找算法可以在一串有序数据中快速查找出所需数据。 int BinarySearch(int* a,int sz,int x)
{int left0,right sz-1;while(leftright){int mid (leftright)/2; //取中间值if(a[mid] x) return mid; //找到与x相等的元素返回下标else if(x a[mid])left mid; //中间值偏小elseright mid; //中间值偏大}return -1; //查找失败
} 二分查找算法的最好情况是第一次就找到目标值此时时间复杂度为O(1)。但是我们评判一个算法的好坏不可能凭其处理问题的最好情况时的复杂度作为参考这是没有意义的。一般来讲我们会以算法的处理最坏情况的时间复杂度作为该算法的时间复杂度。 在最坏的情况下在整个数组中无法找到目标元素。由于二分查找每次取中间值即可排除一半的元素因此可得当输入量为n时二分查找总共需要进行大约为以二为底n的对数次当对数的底数为2时在表示算法的时间复杂度时可计为O(logn)。 因此二分查找的时间复杂度为O(logn)。 3 空间复杂度
3.1 什么是空间复杂度 我们知道程序运行时需要调用内存空间而算法作为程序的一部分同样也需要调用空间。 而空间复杂度就是衡量一个算法执行所需调用空间的大小的标准。 在很多情况下在评判算法的性能好坏时空间复杂度的参考权重比时间复杂度要低得多因此有些算法可能会采取牺牲空间复杂度的方式来换取更低的时间复杂度。但这并不代表空间复杂度不重要。 3.2 空间复杂度的计算 空间复杂度的计算和时间复杂度的计算较为相似在理解了时间复杂度的计算规则后理解空间复杂度的计算应该会比较轻松。我们还是通过例子来分析。 int main()
{int a;return 0;
}
上面这段代码可以说非常简单了总共开辟了两块内存空间一块用来调用main函数另一块存储变量a。由于开辟的空间大小为常数因此该段代码的空间复杂度为O(1)。int* copy(int* a,int sz)
{int* ret (int*)malloc(sizeof(int)*sz);return ret;
} 这是一个复制函数用来将给定的数组复制。在这个函数中当给定数组的大小为n时该函数会开辟一个大小为n的空间用来复制数组因此其空间复杂度为O(n)。 结束语 了解复杂度是学习算法的基础它让我们明白如何判断一个算法的好坏。学会判断复杂度后我们将会知道如何优化算法并学会在不同情景下使用最合适的算法。 以上就是我对复杂度的理解了如内容有误欢迎各位大佬指正。
