gpt4 book ai didi

algorithm - 最大子数组 - 运行时间

转载 作者:塔克拉玛干 更新时间:2023-11-03 03:44:48 25 4
gpt4 key购买 nike

我目前正在分析 maximum subarray problem 用于强力算法和分而治之算法(递归)。

使用蛮力算法,最坏情况下的运行时间为 O(n^2)。使用递归算法,最坏情况下的运行时间为 O(n*log(n))。

但是对于达到某个常数(比如 k)的小输入,暴力实际上更快,所以我想使用暴力直到 k,然后递归。

我不确定如何分析这个,即通过使用参数 n 和 k。(插入/合并排序也有类似的问题,它需要 O(k^2*(n/k))=O(n*k),所以我想我可以使用相同的结果但是......)。


让我尝试重新表述,并使用 theta 符号。

“在递归(使用 n 和 k 作为参数)中使用蛮力的算法的渐近运行时间是多少,其中蛮力比递归快到 k = 50。”

我必须在其中包含参数 n 和 k,而递归树是迄今为止我们测试这些问题的唯一主题。

最佳答案

请记住,大 O 谈论的是算法的长期增长率。形式上,它表示对于足够大的 n,一个函数的行为小于另一个函数的某个常数倍数。这意味着,如果您固定常数 k 的任何选择,然后对 n ≤ k 使用 O(n2) 算法,对所有 n > k 使用 O(n log n) 算法,则整体运行时间将为 O(n log n),因为随着 n 变得足够大,算法的行为完全取决于 O(n log n) 算法的行为。

也就是说,你应该看看Kadane's algorithm ,一种使用 dynamic programming 的算法在 O(n) 的时间、O(1) 的空间中解决这个问题,并且只需遍历数组一次。它几乎肯定会比您的任何一种方法都更快(实际上和渐近)。

希望这对您有所帮助!

关于algorithm - 最大子数组 - 运行时间,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/9650353/

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