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