并行算法的基本设计技术 习题例题： ①试证明：当时，算法6.1的时间复杂度为。 ②令表示Pi中第j段中的元素数，试证明算法6.1在执行过程中，处理器中所积累的元素数目不会超过，即。 ①试举一典型算例，说明Valiant归并算法的执行过程。 ②试分析算法6.2所需的处理器数。 ③试证明算法6.2的时间复杂度为：2loglogn+const。 ①试分析算法6.3的时间复杂度。 ②令A=(0，1，2，7，9，11，16，17，18，19，23，24，25，27，28，30，33，34)，B=(3，4，5，6，8，10，12，13，14，15，20，22，26，29，31)。试按算法6.3，将其进行对数划分，并最终将它们归并之。 ①试证明Batcher定理。 ②画出一个16个输入的双调归并网络。 ①试分析算法6.9的总运算量 ②假定序列为(1，2，3，4，5，6，7，8)，试用算法6.9求其前缀和。 6. 试解释在一维心动阵列上计算卷积时，序列x和y为何要各间隔一拍进入阵列。