0

введите сюда описание изображения

#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;   
}
3
  • 1
    Сформулируйте точнее, что вы хотите. Что должнаделать программа, что она делает, что нет, в чем вопрос. И учтите, что O(2n) и O(n) - это эквивалентные записи. Как и O(3n) или O(123n+18ln(n))...
    – Harry
    31 мая 2020 в 17:00
  • Harry, прикреплена картинка. В ней более наглядно задан вопрос. Там указан алгоритм, который определяет количество минимальных элементов в целочисленном массиве. Мне нужно составить программу так, чтоб временная сложность составленного кода соответствовала O(2*n), и еще одну программу чтоб временная сложность соответствовала O(n). Программа была составлена. Успешно запускается в Dev-C++, но не понятно какую она выполняет временную сложность. Может, чтоб определить временную сложность, нужно создать счетчик, подсчитывающий количество итераций?
    – Muriam
    31 мая 2020 в 17:10
  • 3
    Понятно, что так аффтары как бы делают посыл "как объединить два цикла в один", но вообще формулировка задачи уровня БЕГN.
    – bipll
    31 мая 2020 в 17:17

2 ответа 2

4

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

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

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
  • Спасибо. Этот код будет соответствовать: и для O(2*n), и для O(n), так как они эквивалентны?
    – Muriam
    31 мая 2020 в 17:15
  • 3
    Уверен, преподы хотели не два отдельных прохода по массиву, а один (хотя теоретически сравнений все равно в наихудшем случае будет выполняться два). Но сформулировали они этот вопрос математически некорректно, так как константные множители в понятие O() не входят.
    – Harry
    31 мая 2020 в 17:19
  • @Harry а как тогда правильнее сформулировать задачу?
    – Learpcs
    13 июл 2020 в 4:33
  • 1
    @Learpcs Я бы спросил, как двухпроходный алгоритм преобразовать в однопроходный. Ведь не факт даже, что получится уменьшить количество сравнений!
    – Harry
    13 июл 2020 в 5:59
4

В исходной программе написано два цикла. В первом мы находим минимальный элемент, а во втором подсчитываем количество элементов, равных минимальному.

Ваша задача — сделать то же самое в одном цикле. Например, так:

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

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

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

8
  • спасибо большое
    – Muriam
    31 мая 2020 в 17:19
  • 1
    А O(1) вы никак не получите. В случае произвольного (неупорядоченного) массива сложность меньше O(n) не получится, потому что надо просмотреть все элементы массива.
    – Harry
    31 мая 2020 в 19:29
  • 1
    @Muriam, Harry прав, O(1) для произвольных данных никак не получить. Наименьшее, что я могу придумать, это O(log N) на упорядоченном массиве. В начале массива будет минимальный элемент, а двоичным поиском можно найти следующий элемент, который больше него. 31 мая 2020 в 20:06
  • 1
    @Muriam, O(1) означает, что цикла не должно быть вообще, должно быть одно выражение. Цикл это O(N)..Конкретно в вашей задаче речь идёт о сумме элементов геометрической прогрессии, для этого есть формула. Наберите в гугле сумма геометрическая прогрессия, разберитесь с формулой, и подставьте в неё свои значения 3 и 10. 1 июн 2020 в 8:20
  • 1
    Вам просто надо вычислить n*m*(m+1)/2, каковое выражение при любых m и n вычисляется за одно сложение, 2 умножения и одно деление, т.е. время вычисления не зависит от n и m, а значит, равно O(1).
    – Harry
    1 июн 2020 в 9:50

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.