统计求最大、最小元素的平均比较次数 编写程序,随机产生10个1~20的整数,设计一个高效算法找其中的最大元素和最小元素,并统计元素之间的比较次数。调用该算法执行10次并求元素的平均比较次数

为了编写一个高效的算法来找到一组随机生成的10个1到20之间整数的最大值和最小值，并同时统计比较次数，我们可以采用分治策略。一种常见的做法是利用“一次遍历”的思想，只需一次扫描即可找出最大值和最小值。以下是Python的一种实现：

import random

def find_max_min(arr):
    if len(arr) == 1:  # 基本情况：数组只有一个元素
        return arr[0], arr[0]
    
    mid = len(arr) // 2
    left_max, left_min = find_max_min(arr[:mid])
    right_max, right_min = find_max_min(arr[mid:])
    
    # 使用分治法结合递归结果
    max_val = max(left_max, right_max)
    min_val = min(left_min, right_min)
    
    # 比较次数统计
    comparison_count = len(arr) - 1
    
    return max_val, min_val, comparison_count

# 随机生成10个1到20的整数
random_numbers = [random.randint(1, 20) for _ in range(10)]
max_val, min_val, total_comparisons = find_max_min(random_numbers)

print(f"最大值：{max_val}, 最小值：{min_val}")
print(f"平均比较次数：{(total_comparisons / 10):.2f}")

# 调用多次并计算平均比较次数
for _ in range(9):
    _, _, comparisons = find_max_min(random_numbers)
    total_comparisons += comparisons
average_comparison = total_comparisons / 10
print(f"\n所有10次执行的平均比较次数：{average_comparison:.2f}")

这个算法的时间复杂度是O(n)，因为我们只对数组进行了一次遍历。因此，平均比较次数会随着实验次数的增长而接近理论上的最差情况，即总共有10次比较。