Question

1.3 请说明下列算法的时间复杂度.

1.3请说明下列算法的时间复杂度。
(1) void sf1 (int n)
{ int i, x=0;
for(i=0; i<5; i++)
for(j=1; j<=n; j++)
x+=2;
}

(2) void sf2 (int n)
{ int i, j, x=1;
for (i=0; i<n; i++)
for(j=0; j<n; j++)
x=x*2;

Answer 1

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