数据结构第一章 绪论答案[3]

这是一个递归调用因k的初值为由语句()知每次调用k增故第()语句执行n次()是FOR循环语句在满足()的条件下执行该语句进入循环体()n次加上最后一次判断出界故执行了n+次()也是循环语句当k=时判断n+次(进入循环体()n次)k=时判断n次最后一次k=n时判断次故执行次数是(n+)+n+…+=(n+)(n)/次语句()是()的循环体每次比()少一次判断故执行次数是n+(n)+…+=(n+)(n)/次注意分析时不要把()分析成n次更不是次

(这时i= s=) REPEAT语句先执行循环体后判断条件直到条件为真时退出循环

算法在最好情况下即二进制数的最后一位为零时只作一次判断未执行循环体赋值语句A[i]执行了一次;最坏情况出现在二进制数各位均为(最高位为零因题目假设无溢出)这时循环体执行了n次时间复杂度是O(n)循环体平均执行n/次时间复杂度仍是O(n)

该算法功能是将原单循环链表分解成两个单循环链表其一包括结点h到结点g的前驱结点;另一个包括结点g到结点h的前驱结点时间复杂度是O(n)

第一层FOR循环判断n+次往下执行n次第二层FOR执行次数为(n+(n)+(n)+…+)第三层循环体受第一层循环和第二层循环的控制其执行次数如下表

i= … n

j=n n n n … n

j=n n n n …

… … … …

j=

j=

j=

执行次数为(++…+n)+(++…+n)+…+n=n*n(n+)/n(n)/在n=时f()=执行过程中输出结果为sum=sum=sum=sum=sum=(每个sum= 占一行为节省篇幅这里省去换行)

O(n)m的值等于赋值语句m:=m+的运行次数其计算式为 ()O() ()O(n) ()O(n) ()O(n) ()O(n)

()由斐波那契数列的定义可得

Fn=Fn+Fn

=Fn+Fn

=Fn+Fn

=Fn+Fn

=Fn+Fn

……

=pF+qF

设Fm的执行次数为Bm(m=…n)由以上等式可知Fn被执行一次即Bn=;Fn被执行两次即Bn=;直至F被执行p次F被执行q次即B=pB=qBm的执行次数为前两等式第一因式系数之和即Bm=Bm+Bm再有Bn=和Bn=这也是一个斐波那契数列可以解得

Bm= [( )nm+( )nm+] (m=…n)

()时间复杂度为O(n)

从小到大排列为logn n/+logn n nlogn n+lognn nn+n n/ (/)n n!(n n)

[] [] []