Data structure and Algorithm
  • 序言
  • 大O表示法
  • 递归
  • 线性表
    • 数组
    • 链表
    • 栈
    • 队列
  • 散列表
    • 哈希表
  • 树
    • 简介
    • 前缀树(字典树)
    • 二叉树
  • 图
    • 广度优先搜索
    • 狄克斯特拉算法
  • 算法-查找
    • 二分查找
    • K最近邻算法
    • 贪婪算法
    • 动态规划算法
  • 算法-排序
    • 交换类排序法
    • 插入类排序法
  • 算法-搜索
    • Untitled
  • 算法-复杂度分析
    • Untitled
  • 算法-字符串匹配
    • Untitled
    • Untitled
  • 算法-基本算法思想
    • 其他算法
Powered by GitBook
On this page

Was this helpful?

大O表示法

Previous序言Next递归

Last updated 6 years ago

Was this helpful?

每次介绍算法时,我都将讨论其运行时间。一般而言,应选择效率最高的算 法,以最大限度地减少运行时间或占用空间。

大O表示法是一种特殊的表示法,指出了算法的速度有多快。

例如,假设列表包含n个元素。简单查找需要检查每个元素,因此需要执行n次操作。使用大O表示法, 这个运行时间为O(n)。单位秒呢?没有——大O表示法指的并非以秒为单位的速度。大O表示法 让你能够比较操作数,它指出了算法运行时间的增速。

但大O表示法说的是最糟的情形。因此,你可以说,在最糟情况下,必须查看电话簿中的每个条目,对应 的运行时间为O(n)。这是一个保证——你知道简单查找的运行时间不可能超过O(n)。

O(n)时间意味着查看列表中 的每个元素一次。例如,对乐队列表进行简单查找时,意味着每个乐队都要查看一次。

对数:

下面按从快到慢的顺序列出了你经常会遇到的5种大O运行时间。

  1. O(log n),也叫对数时间,这样的算法包括二分查找。

  2. O(n),也叫线性时间,这样的算法包括简单查找。

  3. O(n * log n),这样的算法包括第4章将介绍的快速排序——一种速度较快的排序算法。

  4. O(n2),这样的算法包括第2章将介绍的选择排序——一种速度较慢的排序算法。

  5. O(n!),这样的算法包括接下来将介绍的旅行商问题的解决方案——一种非常慢的算法。

小结:

  1. 算法的速度指的并非时间,而是操作数的增速。

  2. 谈论算法的速度时,我们说的是随着输入的增加,其运行时间将以什么样的速度增加。

  3. 算法的运行时间用大O表示法表示。

  4. O(log n)比O(n)快,当需要搜索的元素越多时,前者比后者快得越多。