Blick dieses max paarweise ein Produkt zu beschleunigen

ich Programmierung bin sehr neu, so gehen Sie bitte einfach auf mich :)Blick dieses max paarweise ein Produkt zu beschleunigen

Wie kann ich die folgende Python-Code Ausgabe quicker-

n = int(input()) 
a = [int(x) for x in input().split()] 
assert(len(a) == n) 

result = 0 

for i in range(0, n): 
    for j in range(i+1, n): 
     if a[i]*a[j] > result: 
      result = a[i]*a[j] 

print(result)

machen Was Gibt es Optionen, um die Geschwindigkeit zu maximieren?

Quelle

2016-05-23 Deadjam106

Sie versuchen, das maximale Produkt einzelner Integer in einer Liste zu berechnen. Computing-Produkt für jedes Paar hat O (N^2) Zeit Komplexität.

Sie können dies durch Sortieren der Liste auf O (N log (N)) reduzieren.

Sie können dies weiter zur linearen Zeit verbessern, aber ich lasse Sie es herausfinden.

Quelle

2016-05-23 01:57:02

Das Finden von zwei größten Zahlen kann in O (n) erfolgen. Keine Notwendigkeit zu sortieren: http://stackoverflow.com/a/37381709/1090562 –

Wie in der Antwort erwähnt, aber ja. –

'sortierte' gibt bereits eine Liste zurück ... –

Alles, was Sie versuchen, ist, zwei verschiedene Elemente zu finden, deren Produkt das größte ist. Dies geschieht, wenn zwei Zahlen die größten sind. Sie haben also im Prinzip zwei größte Zahlen im Array. Dies kann in O(n) erfolgen.

Ein Beispiel, wie dies getan werden kann. Finde die größte Anzahl und Position. Speichere es, entferne es und finde das Maximum des Ergebnisses (welches das zweitgrößte ist). Jetzt multiplizieren Sie beide.

Quelle

2016-05-23 02:13:20

@YakymPirozhenko Sie haben Recht, In diesem Fall erste 4 Elemente können auch in O (n) gefunden werden. Und dann benutze deine Max Formel. –

Betrachte auch das Produkt der zwei negativsten Zahlen. –

ich sehe, Stepik.org Kurs Lektion "Maximum paarweise Produkt":

die folgenden Versuchen Sie, anstelle der kaskadierten for-Schleife:

n1 = max(a) 
a.remove(n1) 
result = n1*max(a)

, die im wesentlichen den größten Wert in einer Variablen speichert , entfernt es aus der Sequenz und multipliziert es mit dem nun größten Wert der Sequenz (zweitgrößter Wert in der ursprünglichen Sequenz).

Quelle

2017-01-02 08:20:17 mveith

Also, ich sehe, es ist genau das, was @Salvador Dali bereits erklärt :-) – mveith

Das wird nicht funktionieren, wenn die gleichen nein in einer Sequenz wiederholt werden – shining

Meine Lösung würde sortierte und set verwenden, da dieser Algorithmus auch auf doppelte Elemente arbeiten.

x, y = sorted(set(nums))[-2:] 
    print(x * y)

Quelle

2017-05-22 17:17:08 shining

Blick dieses max paarweise ein Produkt zu beschleunigen

Antwort

Verwandte Themen