下面算法的时间复杂度 [英] Time Complexity of below algorithm

问题描述

我是算法，它接受一个数组作为参数，并返回其最大值。

I have is algorithm, which takes an array as an argument, and returns its maximum value.

find_max(as) :=
    max = as[0]
    for i = 1 ... len(as) {
        if max < as[i] then max = as[i]
   }
    return max

我的问题是：因为该数组最初在（均匀）随机排列，它的所有元素都是不同的，什么是对的预期次数的最高变量更新（忽略初始分配）。

My question is: given that the array is initially in a (uniformly) random permutation and that all its elements are distinct, what's the expected number of times the max variable is updated (ignoring the initial assignment).

例如，如果为= [1，3，2] ，更新到 MAX，然后数将1（读值3时）。

For example, if as = [1, 3, 2], then the number of updates to max would be 1 (when reading the value 3).

推荐答案

一个模拟许多不同的数组的大小与多个试验每一个都可以进行分析的：

Empirical Solution

A simulation of many different array sizes with multiple trials each can be performed and analyzed:

#include <iostream>
#include <fstream>
#include <cstdlib>
#define UPTO 10000
#define TRIALS 100

using namespace std;

int arr[UPTO];

int main(void){
  ofstream outfile ("tabsep.txt");
  for(int i = 1; i < UPTO; i++){
    int sum = 0;
    for(int iter = 0; iter < TRIALS; iter++){
      for(int j = 0; j < i; j++){
        arr[j] = rand();
      }
      int max = arr[0];
      int times_changed = 0;
      for(int j = 0; j < i; j++){
        if (arr[j] > max){
          max = arr[j];
          times_changed++;
        }
      }
      sum += times_changed;
    }
    int avg = sum/TRIALS;
    outfile << i << "\t" << avg << "\n";
    cout << "\r" << i;
  }
  outfile.close();
  cout << endl;
  return 0;
}

---

当我作图这些结果，复杂度似乎是对数：

---

When I graphed these results, the complexity appeared to be logarithmic:

我认为它是安全的结论是，时间复杂度为 O（log n）的

I think it's safe to conclude that the time complexity is O(log n).

• 假设数字的范围是0，...，N
• 您有一个初步的最大的m
• 接下来最大将是一个随机数范围为m + 1个... n，这个平均数是（M + N）/ 2
• 这意味着每当你找到一个新的最大值，你是分裂的可能最大值的范围内2
• 反复分裂相当于一个对数
• 因此，次新的最大发现编号为 O（log n）的

• Assume that the numbers are in the range 0...n
• You have a tentative maximum m
• The next maximum will be a random number in the range m+1...n, which averages out to be (m+n)/2
• This means that each time you find a new maximum, you are dividing the range of possible maximums by 2
• Repeated division is equivalent to a logarithm
• Therefore the number of times a new maximum is found is O(log n)

这篇关于下面算法的时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！