大O表示法

大O表示法，表示计算机需要执行的操作总数随着数据量增加的增速。比如：

O(1)表示无论数据量多大，算法需要计算机执行的操作总数总是1次。如果计算机执行1次操作需要10ms（实际计算机执行一次操作所需时间远远小于10ms），则算法的运行时间总是10ms；

O(n)表示，数据量为n，则算法需要计算机执行的操作总数是n次。

常见的大O运行时间

常量

O(n)中的n为c*n，c为常量，比如下面两个函数，大O运行时间都为O(n)。如果数组长度为5，计算机执行每个操作需要10ms，则【函数1】需要50ms，而【函数2】则需要5s。此时【函数2】中的1s就是常量c。

【函数1】遍历数组打印所有数组元素

def print_items(list):

    for item in list:

        print item

【函数2】在每次打印元素前，睡眠1s

from time import sleep

def print_items2(list):

    for item in list:

        sleep(1)

        print item

通常比较算法运行时间时，不考虑常量。因为只要它们的大O运行时间不同，则常量可以忽略不记，比如要查找的列表包含40亿个元素：

简单查找的大O运行时间为O(n)，常量为10ms，则运行时间为463天

二分查找的大O运行时间为O(logn)，常量为1s，则运行时间为32秒

但如果算法的大O运行时间相同，则常量决定了哪种算法更快。比如快速排序在最佳和平均情况下的大O运行时间与合并排序相同，都是O(nlogn)，但快速排序的常量比合并排序小，且虽然快速排序最糟情况下的大O运行时间为O(n2)，但是快速排序遇到最糟情况比遇到平均情况的可能性小得多，所以很多编程语言选择快速排序，比如C语言标准库中的函数qsort。

我的直播间

长期直播学习计算机基础知识
http://live.bilibili.com/22166751
https://www.douyu.com/7391661