分治法查找数组元素的最大值和最小值(python实现)

实验内容

给定任意几组数据,利用分治法的思想,找出数组中的最大值和最小值并输出

实验原理

利用分治法,将一个数组元素大于 2 的数组分成两个子数组,然后对每一个子数组递归调用,直到最小的子数组的元素个数为 1 个或者是 2 个,此时就能直接得出最大值与最小值,然后逐步往上合并子数组,比较 2 个子数组的最大值与最小值,依次进行下去,最后就能找到整个数组的最大值与最小值。

实验步骤

① 先解决小规模的问题,如数组中只有 1 个元素或者只有两个元素时候的情况。
② 将问题分解,如果数组的元素大于等于 3 个,将数组分为两个小的数组。
③ 递归的解各子问题,将中分解的两个小的数组再进行以上两个步骤最后都化 为小规模问题。
④ 将各子问题的解进行比较最终得到原问题的解

代码实现
import time

def findbest(A, low, high):
    if high - low = 1:                 #如果数组中元素只剩下两个,则可以直接比较
        if A[low] = A[high]:
            return A[high], A[low]
        else:
            return A[low], A[high]

    mid = (low + high) // 2             #从中点分成两个子数组,进行递归查找
    result1 = findbest(A, low, mid)
    result2 = findbest(A, mid+1, high)
    if result1[0]  result2[0]:         #比较找到的两个子数组的最大值的大小关系
        if result1[1]  result2[1]:     #再比较找到的两个子数组的最小值的大小关系
            return result2[0], result1[1]   #返回结果(最大值,最小值)
        else:
            return result2[0], result2[1]
    else:
        if result1[1]  result2[1]:
            return result1[0], result1[1]
        else:
            return result1[0], result2[1]

def main():
    from random import sample
    rand_array = sample([x for x in range(-1000, 1000)], 10)#在-1000~999中产生10个随机数
    print(rand_array)
    start = time.time()
    result = findbest(rand_array, 0, 9)
    print("最大值为:%d" %(result[0]))
    print("最小值为:%d" %(result[1]))
    end = time.time()
    print("共耗时:\n" + str(end - start) + " s")


if __name__ == '__main__':
    main()
时间复杂度分析

时间消耗主要在 findbest 函数的执行过程中,因为该函数过程中实际上就是对整个数组进行了一次遍历,那么时间复杂度就是 O(n),n 为输入规模

运行结果
[-246, 559, -696, -618, -519, 650, -619, -38, -288, 410]
最大值为:650
最小值为:-696
共耗时:
0.0 s

[-811, -93, -116, 436, -804, 431, -968, 632, -351, 863]
最大值为:863
最小值为:-968
共耗时:
0.0 s

[-585, 406, -32, 940, 737, 745, 168, -606, -929, -631]
最大值为:940
最小值为:-929
共耗时:
0.0 s
最新回复(0)
/jishueS9_2FXOQwMRDZMbU7w6AXKyMr4BvoAROMFnSCLg_3D_3D4794691
8 简首页