使用python内建函数,如何分析复杂度

发布网友发布时间：2022-04-05 23:39

共1个回答

热心网友时间：2022-04-06 01:09

字典（dict）下列字典的平均情况基于以下假设： 1. 对象的散列函数足够撸棒（robust），不会发生冲突。 2. 字典的键是从所有可能的键的集合中随机选择的。小窍门：只使用字符串作为字典的键。这么做虽然不会影响算法的时间复杂度，但会对常数项产生显著的影响，这决定了你的一段程序能多快跑完。操作平均情况最坏情况复制[注2]O(n)O(n)取元素O(1)O(n)更改元素[注1]O(1)O(n)删除元素O(1)O(n)遍历[注2]O(n)O(n) 注： [1] = These operations rely on the “Amortized” part of “Amortized Worst Case”. Indivial actions may take surprisingly long, depending on the history of the container. [2] = For these operations, the worst case n is the maximum size the container ever achieved, rather than just the current size. For example, if N objects are added to a dictionary, then N-1 are deleted, the dictionary will still be sized for N objects (at least) until another insertion is made.