Articles of Algorithmus

Fast genau bigint faktoriell

Ich habe eine Fixpunkt-Bignumber-Bibliothek und möchte eine schnelle Fakultät ohne Präzisionsverlust implementieren. Nach einigen Mathetricks auf Papier habe ich diese Formel: (4N)!=((2N)!).((2N)!).{ (2N+1).(2N+3).(2N+5)…(4N-1) }.(2^N)/(N!) Das ist schon ziemlich schnell, und mit einigen Programmiertricks nähert sich die Komplexität ~ O(log(n)) . Um es klar zu sagen, meine derzeitige Implementierung ist dies: //————————————————————————— longnum fact(const DWORD &x,longnum […]

Algorithmus zum Finden ähnlicher Bilder

Ich brauche einen Algorithmus, der bestimmen kann, ob zwei Bilder “ähnlich” sind und ähnliche Muster von Farbe, Helligkeit, Form usw. erkennen. Ich könnte einige Hinweise darauf benötigen, welche Parameter das menschliche Gehirn verwendet, um Bilder zu “kategorisieren”. .. Ich habe auf hausdorff basiertes Matching geschaut, aber das scheint hauptsächlich für die Anpassung von transformierten Objekten […]

Datenstruktur für geladene Würfel?

Angenommen, ich habe einen n-seitig geladenen Würfel, bei dem jede Seite k eine gewisse Wahrscheinlichkeit p k hat , wenn ich sie rolle. Ich bin gespannt, ob es einen guten Algorithmus gibt, um diese Informationen statisch zu speichern (dh für einen festen Satz von Wahrscheinlichkeiten), so dass ich einen zufälligen Würfelwurf effizient simulieren kann. Derzeit […]

Effizienz der rein funktionalen Programmierung

Weiß jemand, was die schlimmste asymptotische Verlangsamung ist, die passieren kann, wenn rein funktional programmiert wird, im Gegensatz zu zwingend (dh Nebenwirkungen zuzulassen)? Klärung aus Kommentar von itowlson : Gibt es ein Problem, bei dem der bekannteste nicht-destruktive Algorithmus asymptotisch schlechter ist als der bekannteste destruktive Algorithmus, und wenn ja, um wie viel?

Peak-Signal-Erkennung in Echtzeit-Zeitreihendaten

Update: Der bisher beste Algorithmus ist dieser . Diese Frage untersucht robuste Algorithmen zur Erkennung plötzlicher Spitzenwerte in Echtzeit-Zeitreihendaten. Betrachten Sie den folgenden Datensatz: p = [1 1 1.1 1 0.9 1 1 1.1 1 0.9 1 1.1 1 1 0.9 1 1 1.1 1 1 1 1 1.1 0.9 1 1.1 1 1 0.9 […]

Gibt es einen O (n) Ganzzahl-Sortieralgorithmus?

Die letzte Woche bin ich über dieses Papier gestolpert , wo die Autoren auf der zweiten Seite erwähnen: Beachten Sie, dass dies eine lineare Laufzeit für ganzzahlige Kantengewichte ergibt. Das gleiche auf der dritten Seite: Dies ergibt eine lineare Laufzeit für ganzzahlige Kantengewichte und O (m log n) für eine vergleichsbasierte Sortierung. Und auf der […]

finde alle Teilmengen, die zu einem bestimmten Wert summieren

Bei einer gegebenen Anzahl von Zahlen: {1, 3, 2, 5, 4, 9}, finde die Anzahl der Teilmengen, die zu einem bestimmten Wert summieren (z. B. 9 für dieses Beispiel). Dies ist ähnlich dem Subset-Summenproblem mit dem geringfügigen Unterschied, dass, anstatt zu überprüfen, ob die Menge eine Submenge hat, die zu 9 addiert, wir die Anzahl […]

Breite zuerst Vs Tiefe zuerst

Wenn Sie einen Baum / ein Diagramm durchlaufen, was ist der Unterschied zwischen Breite zuerst und Tiefe zuerst? Beliebige Codierungs- oder Pseudocode-Beispiele wären großartig.

Wie werden SSL-Zertifikate verifiziert?

Welche Schritte sind erforderlich, um ein SSL-Zertifikat sicher zu überprüfen? Mein (sehr begrenztes) Verständnis besteht darin, dass der Server beim Besuch einer https-Site ein Zertifikat an den Client (den Browser) sendet und der Browser die Ausstellerinformationen des Zertifikats von diesem Zertifikat abruft, um dann den Aussteller zu kontaktieren und irgendwie zu vergleichen Zertifikate für die […]

Millionen von 3D-Punkten: Wie finden Sie die 10 von ihnen am nächsten an einem bestimmten Punkt?

Ein Punkt in 3-d ist definiert durch (x, y, z). Der Abstand d zwischen zwei beliebigen Punkten (X, Y, Z) und (x, y, z) ist d = Sqrt [(Xx) ^ 2 + (Yy) ^ 2 + (Zz) ^ 2]. Jetzt gibt es eine Million Einträge in einer Datei, jeder Eintrag ist ein Punkt im Raum, […]