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>第一种算法不是<code>O(log n)</code>,因为它检查每个元素的值。可以证明它是<code>O(n)</code></p> <p>至于第二个,你可能只是在这么小的范围内没有注意到n和nlogn之间的区别。你知道吗</p>
请先
登录
后评论
针对此问题:
更多的回答
关注
89
关注
收藏
1
收藏,
216
浏览
网友 提问于 2天前
相关Python问题
如何合并多个PDF文件?
7 回答
如何合并多个xarray数据变量及其坐标?
10 回答
如何合并多个列中具有重复值的行
3 回答
如何合并多个唯一id
1 回答
如何合并多个图纸并使用图纸名称的名称重命名列名?
5 回答
如何合并多个字典并添加同一个键的值?(Python)
9 回答
如何合并多个搜索结果文件(pkl)以将它们全部打印在一起?
1 回答
如何合并多个数据帧
1 回答
如何合并多个数据帧并使用Pandas为假人添加列?
3 回答
如何合并多个数据帧并按时间戳排序
9 回答
如何合并多个数据帧的列表并用另一个lis标记每列
4 回答
如何合并多个数据框中的列
6 回答
如何合并多个文件?
8 回答
如何合并多个查询集?
7 回答
如何合并多个绘图?
6 回答
如何合并多个词典
9 回答
如何合并多个输入数据集(数据帧)?
9 回答
如何合并多条记录中拆分的文本行
10 回答
如何合并多索引列datafram
5 回答
如何合并多级(即多索引)数据帧?
4 回答