教材81页代码3.20中的List::selectionSort()算法,通过selectMax()在前缀子序列中定位的最大元素max,有可能恰好就是tail的前驱——自然,此时“二者”无需交换。针对这一“问题”,你可能会考虑做些“优化”,以期避免上述不必要的交换,比如将
a)以序列(1980,1981,1982,...,2011,2012;0,1,2,...,1978,1979)为例,这种情况共发生多少次?
b)试证明,在各元素等概率独立分布的情况下,这种情况发生的概率仅为1nn/n→0——也就是说,就渐进意义而言,上述“优化”得不偿失。
A.仿真技术
B.分解协调技术
C.最优化技术
D.网络技术
图11.23是图11.22的C代码的部分三地址代码序列。
(1)请将图11.23的三地址代码序列划分为基术块并做出其流图。
(2)将每个基本块的公共子表达式删除。
(3)找出流图中的循环,将循环不变量计算移出循环外。
(4)找出每个循环中的归的变量, 并在可能的地方删除它们。
基本块的DAG如下图所示,若(1)B在该基本块出口处不活跃,(2)B在该基本块出口处活跃的,请分别给出以下代码经过优化后的代码。