Ermitteln der Big-O dieses Algorithmus

Question

Ich versuche zu verstehen, was der Big-O des folgenden Codes ist.

Was der Code soll

Wesentlichen tun, ich bin versucht, eine Teilmenge (max size = selectionSize) von zufälligen Knoten und alle Kanten zu wählen, die zwischen ihnen besteht. Die Auswahl der zufälligen Knoten erfolgt in der while Schleife. Nachdem ich das getan habe, möchte ich alle Kanten auswählen, die zwischen den ausgewählten Knoten existieren.

Was ich denke, es & Deshalb

Ich denke, die Laufzeit ist O = n^2 wo n=selectionSize. Der Grund ist: Obwohl ich die Größe der Elemente in nodes erhöhen kann (z. B. 10000), glaube ich nicht, dass es den Algorithmus beeinflussen kann, da ich nur das Maximum von selectionSize durchlaufen habe. Der einzige Grund, warum ich ein bisschen besorgt bin, dass das falsch ist, ist wegen der while Schleife, wo ich zufällige Elemente aus der Liste auswähle, bis ich genug habe. Das kann ziemlich lange dauern (weil es zufällig ist), aber ich glaube nicht, dass es die Gesamtleistung in Bezug auf die Zeit beeinflusst. bearbeiten: igitt auf den zweiten Gedanken ... Nevermind ... Die nodes Größe es nicht beeinflusst (da node.getNeighbors() kann höchstens die Größe des nodes sein) .. Also ich denke, dass, wenn die selectionSize gleich die Größe von nodes, die Laufzeit ist O=n^2 wo n=size of nodes.

Alle Tipps/Hinweise wären willkommen.

-Code

// nodes and selectionSize are my input: 
int[] nodes = {1,2,3...,1000}; // 1000 elements 
int selectionSize = 500; // This can be at most the size of the elements (in this case 1000) 

run_algo(nodes, selectionSize); 

public void run_algo(int[] nodes, int selectionSize) { 
    randomNodesList = {}; 

    while(randomNodesList < selectionSize) { 
     randomNode = selectRandomNode(nodes); // Assume O(1) 

     if(!randomNodesList.exists(randomNode)) { // Assume O(1) 
      randomNodesList.push_back(randomNode); // Assume O(1) 
     } 
    } 

    foreach(node in randomNodesList) { 
     foreach(neighbor in node.getNeighbors()) { // Max. nodes size (in this case 1000) 
      if (!randomNodesList.exists(neighbor)) { // Assume O(1) 
       AddEdge(node, neighbor); // Takes O(1) time 
      } 
     } 
    } 
} 

Answer 1

wenn selectRandomNode(nodes); Arbeiten mit Ersatz (der gleiche Knoten zweimal werden kann gepflückt), dann die große o ist not defined, da Sie eine wahrscheinlich Endlosschleife haben (Sie denselben Knoten Kommissionierung immer wieder landen kann).

Wenn es ohne Ersatz funktioniert, dann ist es O(n^2) (im schlimmsten Fall kann jeder Knoten mit jedem anderen Knoten verbunden sein).

---

Hinweise zur Auswahl ersatzlos:

• den Fall betrachten, wenn Sie eine Reihe von Größe n gegeben sind, sagen A und ein leeres Array, B. Alle Elemente in A sind einzigartig.

• Die Aufgabe ist B mit n Elemente zufällig aus A ausgewählt zu füllen. Es ist wünschenswert, dass es mindestens k einzigartige Elemente in B geben sollte.

Es kann gezeigt werden, dass die Wahrscheinlichkeit mehr als k einzigartige Gegenstände des Habens mit zunehmender n (die Gleichungen nach dem Grund habe ich hinzugefügt).

So wird in der Praxis die Wahrscheinlichkeit der Schleife Endbearbeitung in einem einzigen Durchlauf (das heißt in weniger als n Stufen) erhält als die Differenz in n und k erhöht groß. Es ist sehr intuitiv, wenn Sie darüber nachdenken, die Mathematik ist nur Kirsche an der Spitze.

---

def k_numerator(n, k): 
    res = 0 
    sign = 1 
    for i in range(k, 0, -1): 
     pow_term = (i ** n) 
     comb_term = comb(k, i) 
     prod = pow_term * comb_term 
     prod = prod * sign 
     res = res + prod 
     sign = sign * -1 
    return res 

def p_exactly_k(n, k): 
    """ 
    Returns the probability of `B` containing exactly `k` unique elements 
    (also see notes above) 
    """ 

    return (comb(n, k) * k_numerator(n, k))/(n ** n) 

Answer 2

Ich bin nicht 100% sicher, ob ich das richtig verstehen. Aber lassen Sie uns es brechen: Die während -Loop läuft "selectionSize" -mal besten Fall und Worst-Case-n (wobei n die Anzahl der Knoten)

Deshalb ist die Größe von randomNodeList in O (n) ist. In einem einfachen Graphen können Sie O (n-1) Nachbarn haben. So dass die ganze Schleife in O sein muss (n^2) (Wegen des n * (n-1))

Axiom richtig ist. Es ist tatsächlich nicht möglich, eine obere Grenze für diesen Algorithmus zu finden. Es ist nicht deterministisch. Es hängt von Ihren Zufallszahlen ab.