大神，能否为我讲解一下：在长度

大神，能否为我讲解一下：在长度为n的顺序表中查找一个元素，假设需要查找的元素有一半的机会在表中，并且如果元素在表中，则出现在表中每个位置上的可能性是相同的，则在平均情况下需要比较的次数大约为？
解析：因为查找的元素有一半机会在表中，所以二分之一的情况下平均比较次数为二分之n,二分之一情况下平均比较次数为n,总得次数为四分之三n.
解析看不懂呀😵

50%的概率是不存在，那需要对比完全部 n个值才知道不存在。
剩下
50%的概率是存在，存在的情况有可能第一个就找到，也有可能第n个找到。平均为n/2次找到。
期望为 =50%*n+50%*n /2 = 75%n

按照答案的理解，如果已经比较完前n-1个，那么最后一个无需比较肯定就是即比较0次，则比较次数为1+2+3+4+5+6+.......n-1+0=（1+n-1）*n/2=n^2/2
平均次数为n/2
答案为n/2*1/2+n/2=3n/4

扫二维码下载贴吧客户端

下载贴吧APP
看高清直播、视频！

17回复贴，共1页

<<返回excel吧

分享到:

日	一	二	三	四	五	六