大O <数据结构>

大O

---

大O表示法让你能够比较操作数，它指出了算法运行时间的增速

• O (log n )，也叫对数时间 ，二分查找
• O (n )，也叫线性时间
• O (n * log n )，快速排序
• O (n 2 )，选择排序
• O (n !)，旅行商问题的解决方案

绘制16网格所需的操作数将为4
（log 16 = 4）。假设你每秒可执行10次操作，那么绘制该网格需要0.4秒。

（16^2=256）那么绘制该网格需要25.6秒

时间图

1. 大O 启示如下

• 算法的速度指的并非时间，而是操作数的增速
• 谈论算法的速度时，是随着输入的增加，其运行时间将以什么样的速度增加
• 算法的运行时间用大O表示法表示
• O (log n )比O (n )快，当需要搜索的元素越多时，前者比后者快得越多