数据结构与算法时间复杂度计算

Question

如图第二题和第三题时间复杂度的计算
jwkdjdhhurhff

Answer 1

引自免费微信小程序：皆我百晓生

当然，我很乐意帮助你分析这些问题的时间复杂度。

问题2： 对于第二个算法分析题，程序首先读取数组a中的n个元素，时间复杂度为O(n)，这是因为for循环执行了n次。然后进行一次遍历以寻找可能破坏单调性（即升序）的第一个元素位置K，这个过程同样需要遍历数组一次，因此其时间复杂度也为O(n)。但请注意，如果输入的数组是严格单调递增的，则内层while循环不会被执行，所以总的时间复杂度可以认为是单次遍历数组的开销，即 O(n) 。

问题3： 对于第三个问题，这是一个计算阶乘的递归函数。在每次递归调用中，它都将问题规模减半（n/2）。由于每次调用都会将问题规模缩小一半，我们可以根据主定理来分析它的时间复杂度。在这种情况下，由于每次递归调用深度大致等于log_2(n)，因此该递归函数的时间复杂度是 O(log n)。

总结一下：

1. 第二个问题中程序的时间复杂度为 O(n)。
2. 第三个问题中递归计算阶乘函数的时间复杂度为 O(log n)。