要求一个线性表能较快地查找,又能适应动态变化的要求,可以采用哈希查找方法。
分块法:把整个线性表分成若干块进行保存,若动态变化则可以添加在表的尾部(非顺序结构),时间复杂度是O(1),查找复杂度是O(N); 若每个表内部为顺序结构,则可以用二分法将查找时间复杂度降至O(log n),但同时动态变化复杂度则变成O(n).
分块查找,需要分块的部分之间是有序的,块内是否有序无所谓。
顺序法是挨个查找,容易实现,查找时间复杂度是O(n),动态变化时可将保存值放入线性表尾部,则时间复杂度为O(1)
二分法是基于顺序表的一种查找方法,查找时间复杂度为O(log n),若是动态变化的情况,移动次数还是O(n)
温馨提示:答案为网友推荐,仅供参考