分析四个算法的运行时间复杂度 - O记号表示

本文分析了四个算法的运行时间复杂度，并使用O记号表示。

(1) 算法A 算法A把规模为n的问题分成5个子问题，每个子问题的规模为n/2，递归地解决这些子问题，最终把这些子问题合成原问题的解的时间是线性的。 算法A的运行时间可以用递归树来表示，每一层的节点数为5的幂次，树的高度为log5n，因此总的运行时间为O(nlog5n)。

(2) 算法B 算法B把规模为n的问题分成2个子问题，每个子问题的规模为n/2，递归地解决这些子问题，最终把这些子问题合成原问题的解的时间是O(n²)。 算法B的运行时间可以用递归树来表示，每一层的节点数为2的幂次，树的高度为log2n，每个节点的处理时间为O(n)，因此总的运行时间为O(nlog2n) = O(n²)。

(3) 算法C 算法C把规模为n的问题分成9个子问题，每个子问题的规模为n/3，递归地解决这些子问题，最终把这些子问题合成原问题的解的时间为O(n²)。 算法C的运行时间可以用递归树来表示，每一层的节点数为9的幂次，树的高度为log3n，每个节点的处理时间为O(1)，因此总的运行时间为O(9log3n) = O(n²)。

(4) 算法D 算法D把规模为n的问题分成2个子问题，每个子问题的规模为n-1，递归地解决这些子问题，最终把这些子问题合成原问题的解的时间是O(n)。 算法D的递归式为T(n) = 2T(n-1) + O(n)，可以用递归展开法求解，得到T(n) = O(2^n)，因此总的运行时间为O(2^n)。