复杂度分析是估算算法执行效率的方法，公式O(f(n))表示算法的复杂度，此方法即为大O复杂度表示法O(f(n))中n表示数据规模，f(n)表示运行算法所需要执行的指令数。
大O复杂度表示法下面的代码非常简单,求 1,2,3…n 的累加和，我们要做的是估算它的执行效率。
def calc(n): sum_ = 0 for i in range(1，n+1): sum_ = sum_ + i return sum_假设每行代码执行的时间都一样为t，执行第2行代码需要时间t，第3,4行代码运行了n遍，需要的时间为2n*t，这段代码总执行时间为(2n+1)* t
结论：代码执行的总时间T(n)与每行代码的执行次数成正比
看下面的代码，估算该段代码的执行时间:
def calc(n): sum_ = 0 for i in range(n): for j in range(n): sum_ = sum_ + i*j return sum_同样假设每行代码执行的时间都一样为t：执行第2行代码需要时间t，第3行代码运行了n遍，需要时间为n*t，第4、5行代码运行了n2次，需要时间为2n2 * t，执行所有代码的总时间为 (2n2 + n + 1)* t。
结论：代码执行的总时间T(n)与每行代码的执行次数成正比。
用O(f(n))来表示算法复杂度：
def calc(n): sum_ = 0 for i in range(1，n+1): sum_ = sum_ + i return sum_def calc(n): sum_ = 0 for i in range(n): for j in range(n): sum_ = sum_ + i*j return sum_T(n) = O(f(n)) , O表示代码的执行时间T(n) 与 f(n)表达式成比例。
大O复杂度表示法：上面例子中的T(n) = O(2n+1), 另一个 T(n) = O(2n² + n + 1)。大O时间复杂度并不表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势，也叫作渐进时间复杂度(asymptotic time complexity)，简称时间复杂度。
当数据量特别大， 也就是n的取值很大的时候，大O表示法中低阶、常量、系数三部分并不会左右增长趋势，可以忽略。
def calc(n): sum_ = 0 for i in range(1，n+1): sum_ = sum_ + i return sum_def calc(n): sum_ = 0 for i in range(n): for j in range(n): sum_ = sum_ + i*j return sum_上面例子中的T(n) = O(2n+1), 另一个 T(n) = O(2n² + n + 1)，用大O表示法表示上面两段代码的时间复杂度，可以记为O(n)，O(n²)。
算法A： O(n) 执行指令，10000*n
def calc(n): sum_ = 0 for i in range(1，n+1): sum_ = sum_ + I “”” 此处省略n行… … “”” return sum_算法B： O(n²) 执行指令数，10*n2
对比上面两个算法，当 n = 10, n=100 时， 算法B执行的速度更快，n = 1000 时两者速度相当
n = 104 , n = 105, n = 106 ，算法A执行的速度更快的
随着数据规模的进一步增大， 这个差距会越来越大
时间复杂度分析如何分析一段代码的时间复杂度?
在分析一个算法、一段代码的时间复杂度时，只关注循环执行次数最多的那一段代码就可以了。
def calc(n): sum_ = 0 for i in range(n): for j in range(n): sum_ = sum_ + i*j return sum_上面的代码中，我们只需要关注内层for循环的时间复杂度就可以了，内层for循环的两行代码被执行了n2次，所以总的时间复杂度就是O(n²)
总复杂度等于量级最大的那段代码的复杂度
def calc(n): sum_ = 0 for i in range(1，n+1): sum_ = sum_ + i sum_1 = 0 for i in range(1,n+1): for j in range(n): sum_1 = sum_1 + i*j return sum_+sum_1上面的代码分为两部分，分别是求 sum_、sum_1，计算sum_部分的代码段时间复杂度O(n)，计算sum_1部分的代码段时间复杂度为O(n²) ，总的时间复杂度由复杂度最大的部分决定, 所以上面代码复杂度为O(n²)。
嵌套代码的复杂度等于嵌套内外代码复杂度的乘积
def fn(n): sum_ = 0 for i in range(n+1): sum_ = sum_ + i return sum_ def calc(n): sum_ = 0 for i in range(n+1): sum_ = sum_ + fn(i) return sum_上面的代码中第二个函数调用了第一个函数, 如果把fn函数调用当作一个普通操作, 那么第二个函数的时间复杂度为O(n) Fn函数的时间复杂度为O(n)，那么函数整体的时间复杂度为O(n*n) = O(n²)。
当两段代码的数据规模不同时，不能省略复杂度低的部分
def calc(n): sum_ = 0 for i in range(1，n+1): sum_ = sum_ + i sum_1 = 0 for i in range(1,m+1): for j in range(m): sum_1 = sum_1 + i*j return sum_+sum_1上面的代码分为两部分，分别是求 sum_、sum_1，计算sum_部分的代码段时间复杂度O(n)，计算sum_1部分的代码段时间复杂度为O(m2) ，总的时间复杂度由复杂度最大的部分决定, 所以上面代码复杂度为O(m²+n)
免责声明：文章内容来自互联网，本站仅作为分享，不对其真实性负责，如有侵权等情况，请与本站联系删除。
转载请注明出处：怎样进行算法的复杂度分析？ https://www.dachanpin.com/a/cyfx/11021.html