本篇内容主要讲解”如何理解算法的复杂度”,感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷,实用性强。下面就让小编来带大家学习”如何理解算法的复杂度”吧!
<强> 1。动机——为什么需要复杂度分析
事后统计法(也就是把代码运行一遍,通过统计,监控得到运行的时间和占用的内存大小)的测试结果非常依赖测试环境以及受数据规模的影响程度非常大。但是实际上更需要一个不用具体的测试数据就可以估计出算法的执行效率的方法。
<强> 2。大O复杂度表示法
算法的执行效率简单来说就是算法的执行时间。比如下面这段代码的执行时间,假设每行代码执行的时间是一样的,都为,unit_time。在这个假设的基础之上,这段代码的总执行时间为(n + 2) * unit_time。
int 卡尔(int n), {,,,, int sum =, 0;,,,,, int 小姐:=,1,,,,,,for (;小姐;& lt;=, n,, + + i), {,,,,,,,, sum =, sum +,我,,,,,,},,,,,return 总和;,} 通过这个例子,可以看出总执行时间T (n)是与每行代码的执行次数成正比,即可以满足这个公式T (n)=O (f (n)),其中n,是数据规模的大小,f (n)表示每行代码执行的总次,O()表示一个函数,即T (n)与f (n)成正比。在这个例子中T (n)=, O (n + 2),这种方式就被称为大O复杂度表示法。但是实际上,阿大,时间复杂度并不具体表示代码执行真正的执行时间,而是表示代码执行时间随数据规模增长的变化趋势,也叫做渐进时间复杂度,简称时间复杂度。那么,在2 n + 2,这个式子中,系数2和常数2并不左右增长趋势,比如它是线性,并不是会因为系数2或者常数2,改变它线性增长的趋势,因此又可以写成T (n)=O (n)。又比如T (n)=O (n ^ 2),那么表示代码执行时间随数据规模n增长的变化趋势是n,平方。下面这张图是不同时间复杂度,随数据规模增长的执行时间变化
<强> 3。时间复杂度分析
如何对一段代码的时间复杂度进行分析呢?可以采用以下几种方法
只关注循环次数最多的一段代码
因为大 O 复杂度表示法只是表示一种趋势，所以可以忽略掉公式中的常数项、低阶、系数等，只记录一个最大的量级就可以了。因此在分析一个算法、一段代码的复杂度的时候，只需要关注循环次数最多的那一段代码就行了。比如下面这段代码，时间复杂度是 O(n)
int cal(int n) { int sum = 0; int i = 1; for (;i <= n; ++i) { sum = sum + i; } return sum; }加法法则：总复杂度等于量级最大的那段代码复杂度
这个主要是省略掉大 O 复杂度中的低阶项。个人感觉这个方法跟上面的方法有些重合。比如下面这段代码中，可以按照循环分为三个段，第一个段中有个循环，但是循环次数是个常数项，对增长趋势无任何影响，因此时间复杂度是 O(1)，第二段代码的时间复杂度是 O(n)，第三个段代码的时间复杂度是 O(n^2)。这三个段中量级最大的那个时间复杂度也就是整段代码的时间复杂度。
int cal(int n) { int sum_1 = 0; int p = 1; for (; p < 100; ++p) { sum_1 = sum_1 + p; } int sum_2 = 0; int q = 1; for (; q < n; ++q) { sum_2 = sum_2 + q; } int sum_3 = 0; int i = 1; int j = 1; for (; i <= n; ++i) { j = 1; for (; j <= n; ++j) { sum_3 = sum_3 + i * j; } } return sum_1 + sum_2 + sum_3; }如何理解算法的复杂度
