Was ist die zeitliche Komplexität des folgenden Codes und wie kann ich ihn in eine lineare oder logarithmische Zeitkomplexität ändern?

Question

long int num,max,mod,a,i,j; 
cin>>num; 
long int arr[num]; 
for(a=0;a<num;a++) 
{ 
    cin>>arr[a]; 
} 
max=arr[0]%arr[0]; 
for(i=0;i<num;i++) 
{ 
    for(j=0;j<num;j++) 
    { 
     mod=arr[i]%arr[j]; 
     if(mod>max) 
     { 
      max=mod; 
     } 
    } 
} 
cout<<max; 

Ich denke, es ist o (n^n) wenn nicht dann bitte die Zeit Komplexität und wie?
Und zweitens kann der obige Code in lineare oder logarithmische Zeitkomplexität umgewandelt werden. Ich bin neu in Daten-Strukturen und Algorithmen Feld bitte helfen Sie mir, dieses Problem zu lösen.
Es wird großartig, wenn Sie den Code bereitstellen. Danke :)

Answer 1

Ich verstehe nicht, warum Leute unten diese Frage abstimmen. Es ist ziemlich interessant.

Wenn alle Eingaben positive Zahlen sind, ist das gewünschte Ergebnis tatsächlich der zweite Maximalwert. Ich glaube, du kannst es selbst programmieren. Der Beweis ist, dass das Ergebnis eine Zahl mod die maximale Zahl sein muss, während die zweite maximale Zahl mod der größte das optimale Ergebnis ergibt, und es entspricht der zweitgrößten Zahl. Aber seien Sie vorsichtig, wenn es mehr als eine maximale Anzahl gibt, müssen Sie die nächstgrößere überprüfen.

Wenn einige Zahlen negativ sind, kann es ein wenig knifflig sein. Ich nehme an, dass das Ergebnis des Moduls immer positiv ist. (Obwohl in C es nicht so funktioniert, aber Sie können diese negativen Zahlen in diesem Fall einfach ignorieren). Zuerst benötigen wir eine Kopie des Arrays, während alle negativen Zahlen in positive konvertiert werden. Zweitens brauchen wir drei Zahlen aus den beiden Arrays, die zweite maximale positive und die größte negative Zahl (die der 0 am nächsten ist) von der ursprünglichen Anordnung und die größte Anzahl von der zweiten Anordnung (alle in positive umgewandelt). Vergleichen Sie die beiden ersten Zahlen mod die dritte Zahl, geben Sie die größere Zahl aus.

Answer 2

Ich habe Ihren ursprünglichen Code funktioniert, so dass Sie einen Ausgangspunkt haben.

template <class T> 
T maxmod(vector<T> const& arr) 
{ 
    auto max = numeric_limits<T>::lowest(); 
    for(auto x : arr) 
     for (auto y : arr) 
     max = std::max(max, y ? x%y : 0); 
    return max; 
} 

Ihr Problem ist in der Tat sehr interessant und ist abhängig von den Vorzeichen Konventionen der Modulo-Operation (die Implementierung bis zu C++ 03 definiert wurde). Im Allgemeinen sollte es möglich sein, in linearer Zeit gelöst zu werden, indem man maximale Suchen mit einigen Transformationen kombiniert. Hier ist ein erster linearer Versuch

template <class T> 
T my_maxmod(vector<T> arr) // deep copy array because we change it 
{ 
    T max = *std::max_element(arr.cbegin(), arr.cend()); // O(N) 
    assert(max != 0); // TODO 
    std::transform(arr.begin(), arr.end(), arr.begin(), [max](T const& a){ // O(N) 
     return a % max; 
    }); 
    max = *std::max_element(arr.cbegin(), arr.cend()); // O(N) 
    return max; 
} 

Dies funktioniert nicht für alle Eingänge. Und Sie müssen immer noch über negative Zahlen und so weiter nachdenken. Aber es könnte Ihnen einen Ausgangspunkt geben. Hier ist ein Demo

Viel Glück.