您的当前位置:首 页 >> 信息中心

算法分析中常用的几种渐进符号,算法复杂度分析

发布日期:2021-09-22 03:57:15 作者: 点击:
复杂度分析

​算法的复杂度指的是执行该算法的程序在运行时所需要的时间和空间(内存)资源,复杂度分析主要是从时间复杂度和空间复杂度两个层面来考虑。

大O(big O)表示法

​在了解时间复杂度之前,我们需要知道怎么用数学符号将它表示出来。

​我们知道,一个算法的执行时间 = 该算法中每条语句执行时间之和。假设每条语句执行一次所需要的时间为单位时间,那么一个算法的执行时间就和算法中需要执行语句的次数成正比,即是等于所有语句的频度(执行次数)之和。

​用T[n]表示代码的执行时间,n表示数据规模的大小,f(n)表示每行代码执行的次数总和,算法执行时间的公式为:$$T[n] = O(f(n))$$​O表示的是代码执行时间随数据规模增长的变化趋势,也叫做渐进时间复杂度(asymptotic time complexity),简称时间复杂度. 下面我们看一个具体的例子:

public int GetSum(int n){int sum = 0;int i = 0;int j = 0;for(; i < n; i++){sum += i;for(; j < n; j++){sum = sum + i * j;}}return sum;}

​在上面例子中,由于已经假设每条语句执行一次所需时间为单位时间,第3,4,5行执了一次,第6,8行分别执行了n次,第9,11行分别执行了n^2次,可以得出$$T(n) = O(2n^2 + 2n + 3)$$​当n的值非常大时,比如n=100000或者更大时,公式中的低阶,常数和系数三部分并不左右增长趋势,因此可以忽略不计,简单点,我们可以将公式表示为:$$T(n) = O(n^2)$$

很多时候,在求一个算法的时间复杂度时,我们都会将n看作一个很大的数,因此只要它的高阶项,不要低阶项,也不要高阶的系数,在后面的例子中还会有所体现.

时间复杂度分析

​前面我们已经知道了big O表示法的由来以及如何表示,下面我们具体讲解如何计算一段代码的时间复杂度.我们只需要记住它的一条原则:只要高阶项,不要低阶项,也不要高阶项的系数.

​为什么可以这么说呢?因为前面已经说过了,big O表示法只是表示一种变化趋势,当执行次数n变得无穷大时,整个变化趋势基本上是由高阶项所决定的,低阶项对它的影响微乎其微.看下面几个例子

public 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