Leetcode 875吃香蕉的时间复杂度

请问bobo老师，这个问题的时间复杂度应如何分析？在主函数中的二分搜索中，假设piles数组的最大值是M，那么我的理解时间复杂度是O(logM)，因为搜索空间是[1, M]。但是在eatingTime的函数中，还要遍历数组piles，假设数组长度是n，那么时间复杂度是O(n)。所以，可不可以说，这个题目的时间复杂度是O(logM + n)呢？同时空间复杂度是O(1).

讲武德的年轻人 2022-03-15

源自：二分查找法 3-2 编程实现 Leetcode 875

收起

1回答

liuyubobobo 2022-03-15 02:51:01

时间复杂度是 O(nlogM)。

每次二分搜索查到一个值，到要进行一遍 O(n) 的运算，O(n) 的这个运算不是仅仅运行一次，而是运行了 logM 次。所以是 O(nlogM)。

继续加油！：）

收起回答

提问者讲武德的年轻人 #1

哦，对了，eatingTime是在while里面，谢谢！还有一个问题，因为您在程序中直接调用了Arrays.stream().max().getAsInt()来存储右边界r。这里的时间复杂度O(n)不考虑吗？

2022-03-15 02:55:35
liuyubobobo 回复提问者讲武德的年轻人 #2

考虑。但是这个 O(n) 只执行一次，复杂度是 O(n + nlogM)。n 相对于 nlogM 是低阶项，在大 O 意义下可以忽略。当然，你要非写成 O(n + nlogM) 或者 O((logM + 1)*n)，并说明这个 1 来自这个 max 操作，也是可以的，但不是必须且没有必要。

2022-03-15 03:00:03