Python中文
首页
教程
问答
标签
搜索
登录
注册
复杂性与运行时间的实际增长不匹配?(Python)
回答此问题可获得
20
贡献值,回答如果被采纳可获得
50
分。
<p>我在python中运行了2个代码,然后测量了运行所需的时间完成了代码非常简单,只是递归的最大值。在这里: 1你知道吗</p> <pre><code>def max22(L, left, right): if(left>=right): return L[int(left)] k = max22(L,left,(left+right-1)//2) p = max22(L, (right+left+1)//2,right) return max(k,p) def max_list22(L): return max22(L,0,len(L)-1) </code></pre> <hr/> <pre><code>def max2(L): if len(L)==1: return L[0] l = max2(L[:len(L)//2]) r = max2(L[len(L)//2:]) return max(l,r) </code></pre> <hr/> <p>第一个应该在O(logn)中运行(imo),第二个应该在O(n*logn)中运行。 但是,我测量了n=1000,n=2000和n=4000的运行时间, 不知何故,这两种算法的增长似乎都是线性的!这怎么可能?我把复杂性搞错了,还是没事? 谢谢。你知道吗</p>
0 条评论
分类:
Python问答
请先
登录
后评论
默认排序
时间排序
1 个回答
匿名
1天前
擅长:python、mysql、java
<p>仅仅因为一个函数将搜索空间除以2,然后递归地查看每一半,并不意味着它在复杂性中有一个log(n)因子。你知道吗</p> <p>在您的第一个解决方案中,您将搜索空间拆分为2,然后最终检查每一半中的每个<em>元素。与丢弃一半搜索空间的二进制搜索不同,您检查的是两部分。这意味着在搜索过程中不会丢弃任何东西,最终会查看每个元素,使复杂性为O(n)。第二个实现也是如此。你知道吗</p>
请先
登录
后评论
针对此问题:
更多的回答
关注
89
关注
收藏
1
收藏,
216
浏览
网友 提问于 2天前
相关Python问题
如何合并多个PDF文件?
9 回答
如何合并多个xarray数据变量及其坐标?
8 回答
如何合并多个列中具有重复值的行
7 回答
如何合并多个唯一id
2 回答
如何合并多个图纸并使用图纸名称的名称重命名列名?
7 回答
如何合并多个字典并添加同一个键的值?(Python)
1 回答
如何合并多个搜索结果文件(pkl)以将它们全部打印在一起?
9 回答
如何合并多个数据帧
4 回答
如何合并多个数据帧并使用Pandas为假人添加列?
3 回答
如何合并多个数据帧并按时间戳排序
6 回答
如何合并多个数据帧的列表并用另一个lis标记每列
3 回答
如何合并多个数据框中的列
7 回答
如何合并多个文件?
7 回答
如何合并多个查询集?
10 回答
如何合并多个绘图?
3 回答
如何合并多个词典
3 回答
如何合并多个输入数据集(数据帧)?
6 回答
如何合并多条记录中拆分的文本行
1 回答
如何合并多索引列datafram
8 回答
如何合并多级(即多索引)数据帧?
10 回答