侧边栏壁纸
  • 累计撰写 122 篇文章
  • 累计创建 68 个标签
  • 累计收到 1 条评论

目 录CONTENT

文章目录

大O标记法与常见时间复杂度

刘少锋
2019-05-25 / 0 评论 / 0 点赞 / 24 阅读 / 597 字

算法 : 内功心法, 是解决问题的一种思想

时间复杂度 $T(n)$

由于每台机器的性能有所差别,所有其执行相同代码的时间也长短不一,故而推出一种计量方式,统计代码执行基本运算(函数调用需要看其源码的基本运算)的数量(n) 来确定一个算法的优劣,其中基本运算的循环按乘法计算,顺序结构按加法计算,分支结构取最大值

for a in range(0, 1000): 
    for b in range(0, 1000):
        for c in range(0, 1000):
            if a+b+c == 1000 and a**2 + b**2 + c**2:
                print('a,b,c,: {}, {}, {}'.format(a,b,c))

上述代码的时间复杂度为
$T = 1000 * 1000 * 1000 * 2$
那么如果将上述代码中的 1000 改为 2000, 则
$T = 2000 * 2000 * 2000 * 2$
由于上述同样的代码由于不同的参数的 T 都不同,我们便将其统一成 N,这样上述代码的时间复杂度可以表示成:
$T = N * N * N * 2$
同样的我们抓住其主要 “矛盾” ,观其大,再将其简化成
$T= N^3$
这样同一段代码的时间复杂度便不会根据其参数而发生改变了。

大 $O$ 标记法 $O()$

其实和求极限的原理相似,抓住问题的主要矛盾,忽略那些细枝末节,也就像前面的 $T$的最后的样子。

时间复杂度的几条基本规则

  1. 基本步骤: 即只有常数项, 算作 $O(1)$

  2. 基本结构顺序, 条件, 循环

    • 顺序结构: 按加法运算

    • 循环结构: 乘法

    • 分支结构: 取最大值

  3. 判断一个算法效率, 往往只需要关注操作数量的最高次项, 其他次要的忽略

  4. 没特殊说明, 分析的时间复杂度都是最坏时间复杂度

常见的时间复杂度

$T$$O$名称
$12$$O(1)$常数阶
$2n+3$$O(n)$线性阶
$3n^2+2n+1$$O(n^2)$平方阶
$5log2n+20$$O(log(n))$对数阶
$2n+3nlog2n+19$$O(nlog(n))$$nlog(n)$ 阶
$6n3+2n2+3n+4$$O(n^3)$立方阶
$2^n$$O(2^n)$指数阶

MpUo3s

$$
O(1) < O(log(n)) < O(n) < O(nlog(n)) < O(n2)< O(n 2log(n)) < O(n3) < O(2n) < O(n!) < O(n^n)
$$

0

评论区