gpt4 book ai didi

time-complexity - 递归求最大值的时间复杂度是多少

转载 作者:行者123 更新时间:2023-12-04 20:21:41 26 4
gpt4 key购买 nike

我只是想确保我朝着正确的方向前进。我想通过递归拆分数组并找到每个单独数组的最大值来找到数组的最大值。因为我要拆分它,所以它是 2*T(n/2)。因为我必须在最后对 2 个数组进行比较,所以我有 T(1)。
那么我的递归关系会是这样的:

T = { 2*T(n/2) + 1, when n>=2 ;T(1), when n = 1;



因此我的复杂性将是 Theta(nlgn)?

最佳答案

不,不......你每次递归都要花费 O(1) 时间。

那里有多少?

有 N 个叶子,所以你知道它至少是 O(N)。

你需要比较多少才能找到绝对最大值?那是 O(log(N))。

把它们加在一起,不要相乘。 O(N+log(N)) 是你的时间复杂度。

关于time-complexity - 递归求最大值的时间复杂度是多少,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/5787752/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com