时间复杂度为什么用O()表示,有什么英文缩写在里面吗/

Question

时间复杂度为什么用O()表示,有什么英文缩写在里面吗/

Answer 1

这个首先要明确一点,只用到比较的排序算法最低时间复杂度是O(nlogn),而像桶排这样的只需要O(R)(R为桶的大小)
为了证明只用到比较的排序算法最低时间复杂度是O(nlogn),首先要引入决策树.
首先决策树是一颗二叉树,每个节点表示元素之间一组可能的排序,它予以京进行的比较相一致,比较的结果是树的边.
先来说明一些二叉树的性质,令T是深度为d的二叉树,则T最多有2^片树叶.
具有L片树叶的二叉树的深度至少是logL.
所以,对n个元素排序的决策树必然有n!片树叶（因为n个数有n!种不同的大小关系）,所以决策树的深度至少是log(n!),即至少需要log(n!)次比较.
而
log(n!)=logn+log(n-1)+log(n-2)+...+log2+log1
>=logn+log(n-1)+log(n-2)+...+log(n/2)
>=(n/2)log(n/2)
>=(n/2)logn-n/2
=O(nlogn)
所以只用到比较的排序算法最低时间复杂度是O(nlogn).