时间复杂度————被list.insert坑了
<p>今天被一个很简朴的坑到了，还想了很长时间，insert 函数，真的知道它内部执行的操作吗？</p><p>开始实在是在看一本算法的书，书内里给了两段工作内容差不多的伪代码</p>
<p>第一段如下：</p>
data = []
while 另有数据:
x = 下一数据
data .insert(0,x) # 把新数据加到表的最前面
<p>第二段如下：</p>
data = []
while 另有数据:
x = 下一数据
data.insert(len(data),x)# 新数据加在末了
<p> 最开始感觉第二中代码中计算量不是应该比第一段多了一个计算长度的部分吗？应该是最二种时间花费更多，究竟上len(data)斲丧的时间或者说时间复杂度是一个常量级别的，几乎可以忽略</p>
<p>这个地方问题点不是在len(data)上，而是在insert 的执行上，insert 如果从使用上，作用上来思考，超等简朴，就是一个插入，但是这个方法中间的执行，却不是一个常量级的时间复杂度，</p>
<p>是一个线性关系，根据插入的位置和data的大小来确定，但是上面枚举的第一种代码，插入的位置刚好是头部，也就是最前面，简朴思考一下如果做一个插入操作，不消insert方法，自己写一个插入的方法，</p>
<p>就会是把从插入位置到末了一个元素全部向后挪动一位，这个时候时间可以看出来时间花费还是很大的，insert(0,x) 时间复杂度是O(n),而insert (-1,x)时间复杂度是O(l)</p>
<p>第二种代码时间复杂度计算是O(n)，第一种代码时间复杂度计算是O(n^2)，</p>
<p> </p>
<p>总结一下，实在这个坑是因为忘记了insert操作实在也是一种遍历操作，需要花费的时间不是常量级，而是线性级</p>
<p> </p><br><br/><br/><br/><br/><br/>来源：<a href="https://www.cnblogs.com/higer666/p/11688865.html" target="_blank">https://www.cnblogs.com/higer666/p/11688865.html</a>
页:
[1]