Как я могу адаптировать алгоритм поиска в массиве старших и младших чисел к сложности (3n / 2) - 2? - PullRequest
Новая
       81

Как я могу адаптировать алгоритм поиска в массиве старших и младших чисел к сложности (3n / 2) - 2?

0 голосов
/ 01 марта 2019

У меня есть программа, которая ищет наибольшее и наименьшее число в массиве из n элементов на языке C ++.Я хочу уменьшить сложность алгоритма a (3n / 2) - 2, который в настоящее время не соответствует этой сложности.

Эта сложность в худшем случае

Мой вопрос: как можноЯ оставляю этот алгоритм вышеупомянутой формуле сложности?Или что я могу изменить, удалить и добавить, чтобы соответствовать этому условию?

Спасибо.Алгоритм сравнения выглядит следующим образом: 

#include <iostream>
using namespace std;
int main(){
    int arreglo[10] = {9,8,7,6,5,4,3,2,1,0};
    int menor =0, mayor =0, comparaciones=0;
    menor = arreglo[0], mayor = arreglo[0];
    for(int i=1;i<10;i++){
        if(arreglo[i]>mayor){
            mayor = arreglo[i];
        }
        comparaciones++;
        if(arreglo[i]<menor){
                menor = arreglo[i];
        }    
        comparaciones++;
    }
    cout<<"Mayor: "<<mayor<<" Menor: "<<menor<<" Comparaciones: "<<comparaciones;
}

ОБНОВЛЕНИЕ: Алгоритм имеет уравнение сложности 5n-2, я должен снизить его сложность до (3n / 2) - 2

1 Ответ

0 голосов
/ 01 марта 2019

В этом решении используется парадигма Divide and Conquer.

Я основал этот ответ от этого веб-сайта , и там вы можете увидеть объяснение, почему для этого потребуется (3n / 2) - 2 сравнение.

Чтобы понять, как это работает, я предлагаю взять ручку и бумагу и следовать коду, используя меньший ввод (например: {3,2,1,0}). 

#include <iostream>
using namespace std;

int* maxMin(int* values, int begin, int end) {
    int partialSmallest, partialLargest;
    int mid, max1, min1, max2, min2;
    //Here we store Largest/Smallest
    int* result = new int[2];

    //When there's only one element
    if (begin == end) {
        partialSmallest = values[begin];
        partialLargest = values[begin];
    }
    else {
        //There is not only one element, therefore
        //We will split into two parts, and call the function recursively
        mid = (begin + end) / 2;
        // Solve both "sides"
        int* result1 = maxMin(values, begin, mid);
        int* result2 = maxMin(values, mid+1, end);

        max1 = result1[0];
        min1 = result1[1];

        max2 = result2[0];
        min2 = result2[1];
        //Combine the solutions.
        if (max1 < max2)
            partialLargest = max2;
        else
            partialLargest = max1;
        if (min1 < min2)
            partialSmallest = min1;
        else
            partialSmallest = min2;
    }

    result[0] = partialLargest;
    result[1] = partialSmallest;
    return result;
}

int main(){
    int values[10] = {9,8,7,6,5,4,3,2,1,0};
    int* finalResult = maxMin(values, 0, 9);
    cout << "Largest: " << finalResult[0] << " Smallest: " << finalResult[1];
}
...