我目前正在分析蛮力算法和分治算法（递归）的 maximum subarray problem .
使用暴力算法，最坏情况运行时为O（n ^ 2） . 使用递归算法，最坏情况运行时为O（n * log（n）） .
但是对于小输入而言，蛮力实际上更快到达某个常数，比如说k，所以我想用蛮力到k，然后再递归 .
我不确定如何分析这个，即使用参数n和k . （对于插入/合并排序存在类似的问题，其中需要O（k ^ 2 *（n / k））= O（n * k），所以我认为我可以使用相同的结果但是......） .
让我尝试重新制定，并让我们使用theta-notation .
“在递归中使用暴力的算法的渐近运行时间是什么（使用n和k作为参数），其中蛮力比递归到k = 50更快 . ”
我必须在其上包含参数n和k，并且递归树是我们迄今为止测试这些问题的唯一主题 .
1 回答
请记住，大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）空间中解决此问题的算法，并且只需对数组进行一次传递 . 几乎可以肯定，它比你的任何一种方法都要快（实际上和同时也是如此） .
希望这可以帮助！