python - 线性搜索得出算法效率

对于未排序列表上的简单线性搜索，我的课本上说：
为了确定平均情况，您需要在每个可能的位置添加找到目标所需的迭代次数，并将总和除以n。因此，该算法执行（n+n-1+n-2+…+1）/n，或（n+1）/2迭代。
他使用的代码示例如下：

def sequentialSearch(target, lyst):
    """Returns the position of the target item if found, or -1 otherwise."""
    position = 0
    while position < len(lyst):
        if target == lyst[position]:
            return position
        position += 1
    return False

我很难理解他是如何从上面得到（n+1）/2的？

最佳答案

当您遍历列表以到达可能的目标时，可能需要n,n-1,...2,1次尝试才能找到它所以如果你想找到avg病例只需将它们全部相加，除以n.(n+n-1+...+2+1)/n。我们知道这一点。所以我们得到的答案是(n+n-1+...+2+1) = n(n+1)/2这是n(n+1)/2*n作为平均值的情况。
例如，线性搜索

 lyst = [4,5,2,1,6]
 possibilities of targets = 4 or 5 or 2 or 1 or 6
 target = 4
 attemps reqd = 1 as found in first attempt i.e first location
 lyst = [4,5,2,1,6]
 target = 5
 attemps reqd = 2 as found in second attempt i.e second location
 lyst = [4,5,2,1,6]
 target = 2
 attemps reqd = 3 as found in third attempt i.e third location
 lyst = [4,5,2,1,6]
 target = 1
 attemps reqd = 4 as found in fourth attempt i.e fourth location
 lyst = [4,5,2,1,6]
 target = 6
 attemps reqd = 5 as found in fifth attempt i.e fifth location

 sum of all attempts reqired = 1 + 2 + 3 + 4 + 5 = 15
 same as n(n+1)/2 = 5(5+1)/2 = 5*3 = 15

 avg case = (1+2+3+4+5)/n = 15/5 = 3
 same as n(n+1)/2*n = 5(6)/2*5 = (n+1)/2 = 6/2 = 3

平均数是指所有元素除以元素数的总和。

关于python - 线性搜索得出算法效率，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/33851960/