主页 / 问题 / 1134289
Accepted
Muriam
Asked:2020-06-01 00:57:40 +0000 UTC2020-06-01 00:57:40 +0000 UTC

如何按照算法 O(2*n) 和 O(n) 的时间复杂度编写程序？

  • 772

在此处输入图像描述

#include <iostream>
#include <conio.h>
#include <locale>
#include <cstdlib> //для генерации рандомных чисел
#define SIZE 28

using namespace std;


int main()
{
    setlocale(LC_ALL, "rus");

    /* Алгоритм:
    int min=a[0], k=0;
    for (int i=1; i<n; i++)
    if (a[i]<min) 
        min=a[i];
    for (int i=0; i<n; i++)
        if (a[i]==min) 
            k++;
    */  
    /* 
        кол-во минимальных элементов в целочисленном массиве
        при временной сложности алгоритма = O(2*n)
    */ 

    int Arr[SIZE];
    srand(time(0));  

    for (int i=0; i<SIZE; i++)                  // генерация 28 шт случайных чисел, от 0 до 100
        {
            Arr[i] = rand()%100;
            cout << Arr[i] << " ";
        }
        cout << "\n";


    int min = Arr[0], k = 0;                    // реализация алгоритма

    for (int i = 1; i < SIZE; i++)
        if (Arr[i] < min) 
            min = Arr[i];

    for (int i = 0; i < SIZE; i++)
        if (Arr[i] == min) 
            k++;

    cout << "количество минимальных элементов = " << k << endl;
    cout << "\n\n";

    /* 
        найти кол-во минимальных элементов в целочисленном массиве
        при временной сложности алгоритма = O(n)
    */ 


    getch();
    return 0;   
}
c++

2 个回答

  1. Best Answer

    关于补充问题，我只会注意到老师们最近完全失控了-显然，USE巢的小鸡去了老师们……他们胡说八道……

    既然我明白他们真正想问什么，这里就是给你的答案……

    int min = a[0], k = 1;
for(int i = 1; i < n; ++i)
    if (min > a[i])
    {
        min = a[i];
        k = 1;
    }
    else if (min == a[i]) ++k;
    • 4

  2. 原始程序包含两个循环。在第一个中，我们找到最小元素，在第二个中，我们计算等于最小值的元素数量。

    你的任务是在一个循环中做同样的事情。例如，像这样：

    int min = a[0], k = 1;
for (int i = 1; i < n; i++) {
  if (a[i] < min) {
    min = a[i];
    k = 1;
  }
  else if (a[i] == min)
    k++;
}

    在这里，我们将每个下一个元素与最后找到的最小值进行比较。如果新元素小于最小值，则它是新的最小值。我们照此保存并将计数器设置k为 1 - 即找到了一个最小元素。

    如果新元素等于最小值，那么这是最小值的另一个副本，递增计数器。

    在任何其他情况下，此元素大于最小值，无需执行任何操作。

    • 4

相关问题