Bestimmung Big O: 4 verschiedene Zahlen in Array finden bis zu S Summieren

Question

eine Reihe von Zahlen arr und eine Reihe S, 4 verschiedene Zahlen in arr dieser Summe bis zu S.

Schreiben Sie eine Funktion finden Gegeben das bekommt arr und S und gibt ein Array mit 4 Indizes solcher Zahlen in arr.

Die Lösung, die ich entwickelte, besteht darin, rekursiv Kombinationen von Indizes zu erstellen, während sichergestellt wird, dass keine Kombinationen mehr als einmal gezählt werden. Ich beschneiden auch den Suchbaum, indem sichergestellt wird die Größe der Lösungsmenge nicht mehr als 4.

#include <iostream> 
#include <vector> 
using namespace std; 

bool find_sol(vector<int> &N, vector<int> &I, int S, int sum){ 
    if (I.size() == 4) 
    if (S == sum) 
     return true; 
    else 
     return false; 
    for (int i = 0; i < N.size(); ++i){ 
    if (I.empty() || I[I.size()-1] < i){ 
     I.push_back(i); 
     if (find_sol(N,I,S,sum+N[i])) 
     return true; 
     else { 
     I.pop_back(); 
     } 
    } 
    } 
    return false; 
} 

int main(){ 
    int S = 23; 
    vector<int> numbers = {1,3,5,6,7,8,9}; 
    vector<int> indices; 
    find_sol(numbers,indices,S,0); 

    // prints 0, 2, 5, 6 
    for (int i = 0; i < indices.size(); ++i) 
    cout << indices[i] <<" "; 
    cout<<endl; 

    return 0; 
} 

Wie kann ich die Laufzeit dieses Algorithmus bestimmen? Ich habe das Gefühl, es ist etwas wie O (n wähle 4), bin mir aber nicht sicher. Die Lösung sagt mir, die optimale Laufzeit ist O (n^2).

Answer 1

Ihre Lösung ist in der Tat O(nC4) = O(n^4), da es alle möglichen Kombinationen findet und sie auscheckt - und für jede Kombination gibt es konstante zusätzliche Arbeit beteiligt.

Es kann in O(n^2) durchgeführt werden, indem zuerst eine Hash-Tabelle (std::unordered_map) gefüllt wird, wobei die Schlüssel die Summe aller Paare im Array sind und die Werte auf die Indizes dieser Werte zeigen. Diese Karte bevölkern ist O(n^2) durchschnittlicher Fall.

Dann wiederholen Sie alle Paare erneut, und für jedes Paar i,j mit Summe d, finden Sie in der Hash-Map, wenn es einen Eintrag mit Schlüssel S - d gibt.

Vorbehalt: Sie müssen auch sicherstellen, dass dieser Eintrag keinen Index von i,j enthält. Um damit umgehen zu können, könnten Ihre Werte der Karte tatsächlich ein Vektor von Paaren sein.

---

Als Randbemerkung, dieses Problem als subset-sum problem, mit einer Lockerung des mit 4 Elementen genau summiert bekannt ist, dass auf das Ziel (wo das klassische Problem für sie hat keine Grenze)