平均时间复杂度问题．

来源：百度知道 编辑：UC知道 时间：2024/06/22 10:39:15
在二维数组M〔0……n，0……m〕中，访问某个元素的平均时间复杂度为（）
答案为 O（1）
想知道具体的解题方法。谢谢

数组是随机访问的,你要找数组的任何一个元素，只需要知道它的偏移量,比如你这里的M[a][b]就直接找到了,所以就是O(1)常量

再举个例子做比较,比如磁带(录音机的那种) 如果你找到第3个位子的内容,一定要先经过1,2,3.找第4个位子的,就要经过1,2,3,4这样的情况,时间复杂度就是线性递增的了,因此时间复杂度为O(n)

ls说的对，数组的随机存取特性使得访问起一个元素的平均时间复杂度为常数阶

数组的特性就是随机访问，比如你要访问第i行第j列的元素，你就直接M[i][j]就出来了，时间复杂度但让是constant time了