真是O(1)吗？想清楚了没？
2013-01-18 11:21 by 老赵, 15399 visits
摘要：话说写程序的时候我们会用到各种数据结构，但十有八九不会由我们自己从头写起，都会直接拿来用。于是很多人就会记住，譬如HashMap或Dictionary的存取是O(1)的操作，二分查找什么的则是O(log(N))。不过，我们在实践中直接把这些类拿来用的时候，最好也留个心眼，知道这些类内部到底做了些什么，为什么它们能够达到O(1)之类的时间复杂度。我们在了解“理论”的同时也需要注意实践上的细节，例如，其实在实践中O(log(N))其实也是个不比O(1)大多少的时间复杂度，此时可能也需要考虑下“常数”会对性能造成多大影响。
阅读全文
