| 算法的空间复杂度（答案） |
| 作者/cherryqi 时间/2006-8-2 12:54:00 类别/数据结构 查看/ |
 发表评论 以论坛方式查看 |
| 标签：数据结构 |
|
(1)I取值范围从1～n，j取值范围从I+1~n，k取值范围从j+1~n，情况如下表所示： I值 j值 k值 输出语句的执行次数 1 2 3, 4, … ,n n-2 … … … n-1 n 1 n / / 2 3 4,5,…,n n-3 … … … n-1 n 1 n / / … … … … n-2 n-1 n 1 n / / n-1 n / / n / / / 所以，输出语句共执行次数为((n-2)+(n-3)+…+1)+((n-3)+(n-4)+…+1)+…+1 = (n-1)(n-2)/2+(n-2)(n-3)/2+…+1 = (((n-1)2+(n-2)2+(n-3)2+…+12)-((n-1)+(n-2)+(n-3)+….+1))/2 =((n-1)n(2n-1)/6-n(n-1)/2)/2 =(n(n-1)(2n-4))/12=n(n-1)(n-2)/6 (2) ceil(log2n); （1）这个算法完成在一维数组a[n]中查找给定值k的功能。语句三的频度不仅与问题的规模n有关，还与输入实例中a的各元素取值以及k的取值相关，即与输入实例的初始状态复杂有关。若a中没有与k相等的元素，则语句三的频度为n；若a中的第一个元素a[0]等于k，则语句三的频度是常数0。在这种情况下，可用最坏情况下的时间复杂度作为时间复杂度。在此例中即为O(n)。这样做的原因是：最坏情况下的时间复杂度是在任何输入实例上运行时间的上界。 有时,也可能选择将算法的平均(或期望)时间复杂度作为讨论目标。所谓的平均时间复杂度是指所有可能的输入实例以等概率出现的情况下算法的期望运行时间与问题规模的数量级的关系。此例中，以k出现在任何位置的概率相同，都为1/n，则语句三的执行频度为[0+1+2+…+(n-1)]/n=(n-1)/2。它决定了此程序段的平均时间复杂度的数量级为f(n)=n,记作O(n)。 （2）在计算包含调用语句的算法的语句频度时，需考虑到调用发生时在被调用算法中各语句的执行情况。本题所示的递归调用较之非递归调用的分析更为复杂。 由于k等于n是算法的出口条件,不妨首先分析算法pp(n)的简单情况,这时各语句的执行频度分别为:1,n+1,n,0,0,0; 而当k=n-1,n-2,…,1时,语句的执行情况和调度情况,如下表所示。 K 值 不考虑调用时各语句的执行频度 调用情况 语句1 语句2 语句3 语句4 语句5 语句6 n 1 n+1 n 0 0 0 / n-1 1 0 0 3 2 1 pp(n) n-2 1 0 0 4 3 1 pp(n-1) … … … … … … … … 1 1 0 0 n+1 n 1 pp(2) 对于k=1即pp(1)而言，各语句的执行次数还须将调用pp(2)时的执行次数累计到内，pp(2)各语句的执行次数又须将调用pp(3)时执行次数累计到内，……由此可的语句频度如下： 语句１：1+1+…+1=n 语句２：0+0+…+0+(n+1)=n+1 语句３：0+0+…+0+n=n 语句４：(n+1)+n+…+3=(n-1)(n+4)/2 语句５：n+(n-1)+…+2=(n-1)(n+2)/2 语句６：1+1+….+1+0=n-1 算法的时间复杂度可以基于频度最大的语句，应为O(n2)。 |
| 查看该用户更多文章>> |