我想编写一个算法来查找 100000 个数组 100000 的最小值和最大值，大小为 1000，包含从 1 到 1000 的随机数。该算法假设返回比较的平均次数。
假设我使用复杂度为 O(n) 的原始解决方案，平均比较次数应该是多少？ 1999 年还是 2000 年(最小值和最大值)？
我也想问一下如何在cpp中创建一个随机数组。
最佳答案
您必须将每个元素进行两次比较(一次与当前最小值比较，一次与当前最大值比较)。
这并不“天真”，这是找到未排序数字的最小值和最大值的最佳方法。
关于c++ - 找出平均比较次数，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/49471942/