Tag: big-o
Die Big-O-notation zur Darstellung der asymptotischen oberen Schranken. Es beschreibt die relevanten Zeit-oder Raum-Komplexität von algorithmen. Big-O-Analyse stellt eine grobe und vereinfachte Schätzung eines Problems Schwierigkeiten.
In Groß-O-notation für Baum-Strukturen: Warum tun einige Quellen beziehen sich auf O(logN) und einige auf-O(h)?
5 Antworten
In der Erforschung der Komplexität für jeden Algorithmus durchsucht einen binären Suchbaum, ich sehe zwei verschiedene Möglichkeiten, etwas auszudrücken: Version #1: Die traversal Algorithmus im worst-case vergleicht einmal pro Höhe des Baumes; daher Komplexität ist O(h). Version
Unterschied zwischen O(m+n) und O(mn)?
3 Antworten
War ich versucht zu finden, die Komplexität eines Algorithmus über verschiedene Ansätze. Mathematisch stieß ich auf ein O(m+n) und anderen O(mn) Ansatz. Aber ich bin nicht in der Lage zu begreifen, oder zu sagen, diese sichtbar zu
Die amortisierten Komplexität von std::next_permutation?
3 Antworten
Ich habe gerade gelesen diese andere Frage über die Komplexität von next_permutation und während ich bin zufrieden mit der Antwort (O(n)), es scheint, wie der Algorithmus möglicherweise haben Sie einen schönen amortisierten Analyse, die zeigt, dass eine
Big O-Komplexität von algorithmen - LZW und Huffman
2 Antworten
Was sind die Raum-und Zeit-Komplexität, in Big O-notation, für die Lempel-Ziv-Welch und Huffman-Komprimierung-algorithmen? Google versagt mir. Dank, Francisco Haben Sie eine Implementierung zu beachten? Bitte poste code. InformationsquelleAutor F. P. | 2011-05-31
Big-Oh-Notation - formale definition
5 Antworten
Bin ich beim Lesen ein lehrbuch jetzt für meine Java-III-Klasse. Wir Lesen über Big-Oh, und ich bin ein wenig verwirrt durch seine formale definition. Formale Definition: "Eine Funktion f(n) ist höchstens g(n), also f(n) = O(g(n)) -
array_unique vs array_flip
4 Antworten
Wenn ich ein array von Ganzzahlen mit Vorzeichen.e.g: Array ( [0] => -3 [1] => 1 [2] => 2 [3] => 3 [4] => 3 ) Einzigartige Werte würde ich instinktiv zu nutzen array_unique aber nach überlegung,
Big O-Analyse mit Rekursion Tree of Art Handlanger
5 Antworten
Ich bin auf der Suche nach die Große O für Handlanger Sortieren. Aus Wikipedia algorithm stoogesort(array L, i = 0, j = length(L)-1) if L[j] < L[i] then L[i] ↔ L[j] if j - i > 1
Big-O-notation für if-Anweisungen?
1 Antworten
Ich Frage mich, was die Groß O notation für diese wäre. Ich kenne die for-Schleife ist O(n). Ich war nicht sicher, ob die if-Anweisungen wurden O(n log n). Wenn dem so ist, machen nicht, dass die Laufzeit-Komplexität
Schwierigkeiten zu verstehen, little-o-notation Beispiel
3 Antworten
Ich Probleme habe mit dieser ein problem 9n <= cn^3 grundsätzlich kann ich runter, um 9/c <= n^2 Aber wie löse ich den rest? Es ist eigentlich 9n <= o(n^3) Ja, Lesen Sie es erneut ich verstehe.
Die Komplexität bei der Erzeugung aller Kombinationen
4 Antworten
Interview Fragen, wo ich anfangen mit "das könnte gelöst werden, indem die Generierung aller möglichen Kombinationen für die array-Elemente" sind in der Regel gemeint, um mich zu finden, etwas besser. Trotzdem möchte ich hinzufügen, "ich würde auf
Zeit Komplexität O() von isPalindrome()
12 Antworten
Habe ich diese Methode, isPalindrome(), und ich bin versucht, die Zeit zu finden Komplexität der it, und auch schreiben Sie den code effizienter zu gestalten. boolean isPalindrome(String s) { boolean bP = true; for(int i=0; i<s.length(); i++)
Gegeben ein array, finde ich in O(n) die längste Spektrum, dessen Endpunkte sind die größten Werte in der range?
7 Antworten
Für ein gegebenes array von zahlen, finden die maximale Entfernung zwischen 2 Punkten (i und j) haben höhere Werte als jedes element zwischen Ihnen. Beispiel: Werte: 0 10 8 9 6 7 4 10 0 index :
Verständnis, Wie Oft Verschachtelten Schleifen Ausgeführt Werden
6 Antworten
Ich versuche zu verstehen, wie oft die Anweisung "x = x + 1" ausgeführt wird in den folgenden code als eine Funktion der "n": for (i=1; i<=n; i++) for (j=1; j<=i; j++) for (k=1; k<=j; k++) x
Zeitkomplexität von algorithmen zur Sortierung
4 Antworten
Ich habe zwei Fragen bezüglich der Zeit-Komplexität. 1) ich habe noch nicht zu haben scheinen, bekommen hold von der big-oh oder die landau-notation. Ich weiß, es wird verwendet, um repräsentieren die Zeit, die Komplexität, aber warum kann
Worst-Case Zeit-Komplexität für einen Algorithmus
6 Antworten
Was ist das Worst-Case Zeitkomplexität t(n) :- Ich lese dieses Buch über algorithmen und als ein Beispiel wie man die T(n) für .... wie die Auswahl-Sort-Algorithmus Wie wenn ich den Umgang mit dem selectionSort(A[0..n-1]) //sorts a given
Die Bestimmung der Zeit-und Raum-Komplexität
2 Antworten
Ich bin mit einigen Schwierigkeiten Bestimmung der Raum-und Zeit-Komplexität. Zum Beispiel, wenn ich einen Baum mit einer Verzweigung Faktor b und haben bei den meisten eine Tiefe d, wie kann ich die Berechnung der Zeit-und Raum-Komplexität? Ich
Wie Sie wissen, wenn Big O ist Logarithmisch?
5 Antworten
Meine Frage aus dem post "Plain-Englisch Erklärungen von Big O". Ich weiß nicht, die genaue Bedeutung von logarithmische Komplexität. Ich weiß, dass ich eine regression zwischen der Zeit und der Anzahl der Operationen, und berechnen Sie die
Vergleichen Sie Big O Notation
2 Antworten
In n-element array-Sortierung und Verarbeitung; in X-Algorithmus: 10-8n2 sec, in Y-algoritm 10-6n log2n sec, in Z algoritm 10-5 Sek. Meine Frage ist, wie kann ich Sie miteinander vergleichen. Zum Beispiel für y arbeitet schneller nach x, Was
Big O-notation für exponentielle und logarithmische Komplexität
1 Antworten
Es gibt eine Menge von Fragen über die big-O-notation, aber bisher fand ich keine klare Antwort für diese Frage. Schreiben wir, dass: O(5n) = O(n) und O(3n^2 + n + 2) = O(n^2) Können wir schreiben, dass:
Komplexität zum einfügen in die Warteschlange
1 Antworten
Betrachten Sie den folgenden code, das erscheint, die ersten 2 Elemente aus der priority-queue, fügt Sie hinzu und fügt die Summe zurück zu priority queue. while (pq.size() > 1) { //Extract shortest two ropes from pq int
Was bedeutet "log*" zu bedeuten?
4 Antworten
Habe ich auf den Begriff gekommen O(log* N) in einem Buch lese ich über Daten-Strukturen. Was bedeutet log* bedeuten? Ich kann nicht finden Sie es auf Google, und WolframAlpha versteht es nicht, entweder. "Ich kann ihn nicht
Big Oh (n log n)
4 Antworten
Ich studiere zurzeit grundlegende algorithmen für die Big-Oh. Ich Frage mich, wenn jemand kann mir zeigen, wie der code für (n log n) in Java mit Big Oh wäre wie oder mich direkt auf jeder Seite SO,
n^2 log n Komplexität
5 Antworten
Ich bin gerade ein bisschen verwirrt. Wenn die Zeit-Komplexität eines Algorithmus ist gegeben durch was ist das in big O-notation? Nur oder halten wir das melden? InformationsquelleAutor darxsys | 2014-02-02
Big-O list-slicing
3 Antworten
Sagen, ich habe einige Python-Liste my_list enthält N Elemente. Einzelne Elemente werden indiziert durch die Verwendung my_list[i_1], wo i_1 ist der index des gewünschten Elements. Jedoch, Python-Listen können auch indiziert werden my_list[i_1:i_2] wo eine "Scheibe" von der
Ist die Zeit, die Komplexität der leer-Algorithmus O(0)?
13 Antworten
So gegeben, das folgende Programm: Ist die Zeit, die Komplexität des Programms O(0)? In anderen Worten, 0 ist A(0)? Ich dachte, die Antwort auf diese in einer separaten Frage beleuchten diese Frage. EDIT: Viele gute Antworten hier!
Was ist die Zeitkomplexität von array.splice() in Google Chrome?
2 Antworten
Wenn ich Sie entfernen ein element aus einem array mit splice() etwa so: arr.splice(i, 1); Wird dies O(n) im schlimmsten Fall, denn es verschiebt alle Elemente nach ich? Oder ist es Konstante Zeit, mit einigen verlinkten Liste
Big-O-notation Suche nach c und n0
4 Antworten
Habe ich nur eingeführt, um Big-O notation und ich habe da einige Fragen. Allerdings bin ich verwirrt, wie, um zu bestimmen, den Wert von n0. Ich habe, um zu zeigen, dass 3n^3 +20n^2 + 5 ist O(n^3).
Ein Werkzeug für die Berechnung der big-O-Zeit-Komplexität von Java-code?
2 Antworten
Ich habe eine Frage in Bezug auf die Zeit-Komplexität (big O notation) für Java-software. Gibt es eine Möglichkeit, schnell zu berechnen, oder es zu testen (oder jede website, die rechnen konnte, es wäre mir willkommen). Zum Beispiel
Warum ist der Zugriff auf ein element eines dictionary-key O(1) - selbst wenn die hash-Funktion kann nicht in O(1)?
8 Antworten
Ich sehen, wie Sie Zugriff auf Ihre Sammlung von Schlüssel. Jedoch die hash-Funktion selbst hat viele Operationen hinter den kulissen, nicht wahr? Vorausgesetzt, Sie haben eine gute hash-Funktion, die ist sehr leistungsfähig, es kann noch immer nehmen
Laufzeit von Algorithmus A ist mindestens O(n2) - Warum ist es sinnlos?
10 Antworten
Warum ist die Aussage: Die Laufzeit von Algorithmus A ist mindestens O(n2) bedeutungslos ist ? Die Laufzeit von Insertion-sort-Algorithmus ist höchstens O(n2) Ist es Richtig? Ich habe versucht, das net, aber konnte nicht eine gute Erklärung. Habe
Effizient ermitteln der Schnittmenge, die eine variable Anzahl von Sätzen von Saiten
7 Antworten
Ich habe eine variable Anzahl von ArrayList ' s, die ich finden muss, die Kreuzung. Eine realistische Obergrenze für die Anzahl der Sätze von Zeichenfolgen ist wahrscheinlich rund 35 aber könnte noch mehr sein. Ich will nicht
Die Lösung der Wiederholung, T(n) = 2T(sqrt(n))
2 Antworten
Möchte ich löse die folgenden recurrence relation: T(n) = 2T(√n); Ich vermute, dass T(n) = O(log log n), aber ich bin mir nicht sicher, wie dieses zu beweisen. Wie würde ich zeigen, dass diese Wiederholung löst den
Big O der Hash-Tabelle vs. Binäre Suche (binary Tree
6 Antworten
Was würde länger dauern? drucken Sie alle gespeicherten Elemente in einem binären Suchbaum in sortierter Reihenfolge oder drucken Sie alle gespeicherten Elemente in einer hash-Tabelle sortiert. Es würde länger dauern, um zu drucken, die Elemente in einer
Was ist die Komplexität dieser dreifach geschachtelte for-Schleife?
5 Antworten
Habe ich ein wenig gesucht auf StackOverflow und haben verstanden, die Komplexität bis zu dem Punkt, der die j-Schleife, die O(n2). Aber mit der verschachtelten neben der k-Schleife, ich bin verwirrt, warum die Komplexität wird O(n3). Kann
Wie berechne big-theta
3 Antworten
Kann jemand geben Sie mir eine Echtzeit-Beispiel dafür, wie zu berechnen big theta. Ist groß theta einige Sache wie der Durchschnittliche Fall (min-max)/2? Ich meine (minimalen Zeit - big O)/2 Bitte korrigieren Sie mich, wenn ich falsch
Kann mir jemand erklären, wie Big-Oh arbeitet mit Summen?
5 Antworten
Ich weiß, das ist nicht unbedingt eine Frage der Programmierung, aber es ist eine informatik Frage, also ich bin in der Hoffnung das mir jemand helfen kann. Habe ich gearbeitet, auf meine Hausaufgaben Algorithmen und herauszufinden, die
Verkettete Liste einfügen Laufzeit Verwirrung
7 Antworten
Ich habe versucht, um zu bestätigen, die Laufzeit für das einfügen für verkettete Listen und es scheint, wie es gibt zwei verschiedene Antworten. Einfügen eines Elements am Ende einer verketteten Liste, ich würde denken, dass es dauern
Wir hängen ein Objekt zu einer Liste in R in amortisiert konstanter Zeit, O(1)?
16 Antworten
Wenn ich einige R-Liste mylist können Sie hängen ein Element obj zu es so auf: mylist[[length(mylist)+1]] <- obj Aber sicherlich gibt es einige mehr kompakt. Wenn ich war neu an der R, habe ich versucht zu schreiben
O(log n) - Algorithmus für die Suche nach max von array?
9 Antworten
Muss ein Algorithmus existieren, der findet das maximum von einem unsortierten array in O(log n) Zeit? Ja: Wenn es entweder aussortiert, oder Sie haben eine sehr große Anzahl von Kernen/Prozessoren. möglich, Duplikat der so finden Sie maximale
Ich brauche Hilfe beweisen, dass wenn f(n) = O(g(n)) impliziert 2^(f(n)) = O(2^g(n)))
2 Antworten
In einem vorherigen problem, zeigte ich (hoffentlich richtig), dass f(n) = O(g(n)) impliziert lg(f(n)) = O(lg(g(n))) mit hinreichenden Bedingungen (z.B. lg(g(n)) >= 1, f(n) >= 1, und hinreichend große n). Nun, ich brauche, um zu beweisen ODER
Am besten Algorithmus für das löschen der Duplikate in array von strings
6 Antworten
Heute in der Schule die Lehrerin bat uns, zu implementieren, die ein Duplikat-Löschung Algorithmus. Es ist nicht so schwierig, und jeder kam mit der folgenden Lösung (pseudocode): for i from 1 to n - 1 for j
Was ist die Big-O für SQL-select?
3 Antworten
Was ist die Big-O für SQL-select für eine Tabelle mit n Zeilen und für die will ich zurück m Ergebnis? Und Was ist die Big-O für eine Update oder delete oder Create Betrieb? Spreche ich über den
Was ist der Best/Worst/Average Case Big-O Laufzeit einer Trie-Datenstruktur?
3 Antworten
Was ist der best/worst/average case Komplexität (Big-O-notation) einer trie-Datenstruktur, die für einfügen und suchen? Ich denke, es ist O(K) für alle Fälle, wo K ist die Länge einer beliebigen Zeichenkette, die eingefügt oder gesucht. Wird jemand dies
Nachweis und Disproving BigO
1 Antworten
Beweisen und disproving Big O Fragen, die explizit sagen, die definition zu beweisen und zu widerlegen, meine Frage ist, ist das, was ich Tue, richtig? Beispielsweise du hast eine Frage, ist g(n) = O(f(n)) ... um es
Was ist Big O einer Schleife?
6 Antworten
Ich war Lesung über Big O-notation. Sie erklärte, The big O einer Schleife wird die Anzahl der Iterationen der Schleife in Anzahl der Anweisungen innerhalb der Schleife. Hier ist ein code-snippet, for (int i=0 ;i<n; i++) {
Warum ist konstant immer sank von big O Analyse?
6 Antworten
Ich versuche zu verstehen, einen bestimmten Aspekt von Big O Analyse im Rahmen der Laufenden Programme auf einem PC. Angenommen ich habe ein Algorithmus, der eine Leistung von O(n + 2). Hier, wenn n wird wirklich groß,
Datenbank-Indizes und Ihre Big-O-notation
5 Antworten
Ich versuche zu verstehen, die Leistung von Datenbank-Indizes in Bezug auf die Groß-O-notation. Ohne zu wissen viel über es, ich würde vermuten, dass: Abfragen in einer primary key-oder unique-index geben Sie einen O(1) lookup-Zeit. Abfragen auf einen
Das Große O auf der Dijkstra Fibonacci-heap Lösung
2 Antworten
Vom Wikipedia: O(|E| + |V| log|V|) Vom Big O-Cheat-Liste: O((|V| + |E|) log |V|) Ich halte es da einen Unterschied zwischen E + V log V und (E+V) log V, gibt es nicht? Weil, wenn Wikipedia die
Konstante Zeit Amortisiert
5 Antworten
Was ist gemeint mit "Konstant Fortgeführten Zeit" beim reden über die Zeit-Komplexität eines Algorithmus? mortoray.com/2014/08/11/what-is-amortized-time InformationsquelleAutor VarunGupta | 2008-10-14
Implementieren Sie eine queue, in die push_rear(), pop_front() und get_min() sind alle Konstanten Zeit-Operationen
11 Antworten
Stieß ich auf diese Frage: Implementieren Sie eine queue, in die push_rear(), pop_front() und get_min() sind alle Operationen Konstante Zeit. Ursprünglich habe ich daran gedacht, mit einem min-heap-Datenstruktur, die O(1) Komplexität für eine get_min(). Aber push_rear() und