Как составить программу в соответствии с временной сложностью алгоритма O(2*n) и O(n)?

Question

#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;   
}

Answer 1

По дополненному вопросу замечу только, что преподы в последнее время стали совсем из рук вон плохи - видимо, пошли в преподы птенцы гнезда ЕГЭшного... Написали ерунду...

Поскольку я понимаю, что на самом деле они хотели спросить, то вот вам ответ...

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;

Answer 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 — то есть найден один минимальным элемент.

Если новый элемент равен минимуму, то это ещё одна копия минимума, увеличиваем счётчик.

В любом другом случае это элемент больше минимума, ничего делать не надо.

БЛОГ НА HUSL

Как составить программу в соответствии с временной сложностью алгоритма O(2*n) и O(n)?

Ответы (2 шт):