Haben Sie sich Komplexitätstheorie im wirklichen Leben?

Question

ich einen Kurs in der Rechenkomplexität zu nehmen und haben bisher den Eindruck hatte, dass es nicht viel helfen einem Entwickler sein wird.

Ich könnte falsch sein, aber wenn Sie auf diesem Weg vorangegangen sind, könnten Sie bitte ein Beispiel dafür, wie die Komplexitätstheorie helfen Ihnen bei Ihrer Arbeit zur Verfügung stellen? Tonnen Dank.

Answer 1

O (1): Normalcodes ohne Schleifen. Nur fließt. Lookups in einer Lookup-Tabelle ist O (1), zu.

O (log (n)): effizient optimierte Algorithmen. Beispiel: Binärbaum-Algorithmen und binäre Suche. Normalerweise tut nicht weh. Du hast Glück, wenn Sie einen solchen Algorithmus zur Hand haben.

O (n): eine einzige Schleife über Daten. Hurts für sehr große n.

O (n * log (n)): ein Algorithmus, der eine Art Kluft tut und Strategie erobern. Hurts für große n. Typisches Beispiel: Mergesort

O (n * n): eine verschachtelte Schleife von einer Art. Hurts auch bei kleinen n. Gemeinsam mit naiven Matrixberechnungen. Sie wollen diese Art von Algorithmus zu vermeiden, wenn Sie können.

O (n ^ x für x> 2): eine schlechte Konstruktion mit mehreren verschachtelten Schleifen. Hurts für sehr kleine n.

O (x ^ n, n und schlimmer!): Ausgeflippt (und oft auch rekursiv) Algorithmen Sie nicht wollen, außer in sehr kontrollierten Fällen in der Produktion Code haben, für sehr klein n und wenn es wirklich keine bessere Alternative . Rechenzeit kann explodiert mit n = n + 1.

Ihr Algorithmus Der Übergang von einer höheren Komplexitätsklasse nach unten können Ihr Algorithmus fly machen. Denken der Fourier-Transformation, die eine O (n * n) Algorithmus hat, der mit 1960 Hardware außer in seltenen Fällen unbrauchbar war. Dann Cooley und Tukey machten einige clevere Komplexität Senkungen durch die Wiederverwendung von bereits berechneten Werten. Das führte zu der weit verbreiteten Einführung von FFT in Signalverarbeitung. Und am Ende ist es auch, warum Steve Jobs ein Vermögen mit dem iPod gemacht.

Ein einfaches Beispiel: Naive C-Programmierer schreiben, diese Art von Schleife:

for (int cnt=0; cnt < strlen(s) ; cnt++) {
  /* some code */
}

Das ist ein O (n * n) Algorithmus aufgrund der Implementierung von strlen (). Nesting Schleifen führen die Komplexität in dem Big-O Multiplikation. O (n) im Inneren O (n) verursacht O (n * n). O (n ^ 3) innerhalb O (n) verursacht O (n ^ 4). In dem Beispiel wird sofort die Stringlänge Vorberechnung dreht die Schleife in O (n). Joel hat auch darüber geschrieben.

Doch die Komplexitätsklasse ist nicht alles. Sie müssen ein Auge auf die Größe von n. Nacharbeiten ein O (n * log (n)) Algorithmus O (n) wird nicht helfen, wenn die Anzahl der (jetzt linear) Anweisungen massiv aufgrund der Überarbeitung wächst. Und wenn n klein ist sowieso, Optimierung wird nicht viel Knall geben, auch.

Answer 2

Es ist zwar richtig, dass man ohne das geringste Verständnis der algorithmischen Komplexität wirklich weit in der Software-Entwicklung zu bekommen. Ich finde ich meine Kenntnisse der Komplexität die ganze Zeit; aber an diesem Punkt ist es oft ohne es zu merken. Die beiden Dinge, die über die Komplexität Lernen Sie als Software-Entwickler gibt es eine Möglichkeit, nicht-ähnliche Algorithmen zu vergleichen, die das gleiche tun (Sortieralgorithmen sind das klassische Beispiel, aber die meisten Menschen ihre eigene Art eigentlich gar nicht schreiben). Je mehr nützliche Sache, die es Ihnen gibt, ist ein Weg, um schnell einen Algorithmus zu beschreiben.

Betrachten wir zum Beispiel SQL. SQL wird jeden Tag durch eine sehr große Anzahl von Programmierern verwendet. Wenn Sie die folgende Abfrage, um zu sehen waren, Ihr Verständnis für die Abfrage ist sehr unterschiedlich, wenn Sie die Komplexität studiert haben.

SELECT User.*, COUNT(Order.*) OrderCount FROM User Join Order ON User.UserId = Order.UserId

Wenn Sie Komplexität studiert haben, dann würden Sie verstehen, wenn jemand sagte, es sei O (n ^ 2) für ein bestimmtes DBMS. Ohne Komplexitätstheorie, würde die Person über Tabellen-Scans und so erklären. Wenn wir einen Index der Order-Tabelle hinzufügen

CREATE INDEX ORDER_USERID ON Order(UserId)

Dann wird die obige Abfrage könnte sein, O (n log n), die einen großen Unterschied für einen großen DB machen würde, aber für einen kleinen, ist es nichts.

Man könnte, dass die Komplexitätstheorie argumentieren nicht verstehen benötigt, wie Datenbanken arbeiten, und sie wäre richtig, aber gibt Komplexitätstheorie eine Sprache für das Nachdenken über und sprechen über Algorithmen, die auf Daten arbeiten.

Answer 3

Für die meisten Arten von Programmierarbeiten der Theorieteil und Beweise für sich genommen nicht geeignet sein können, sondern was sie tun, ist zu versuchen, Ihnen die Intuition in der Lage, sofort zu sagen: „Dieser Algorithmus ist O (n ^ 2), so wir können es nicht auf diese eine Million Datenpunkte laufen“. Auch in der elementarsten Verarbeitung von großen Datenmengen werden Sie in diesen ausgeführt werden.

schnell Komplexitätstheorie Denken ist wichtig für mich in Geschäftsdatenverarbeitung, GIS, Grafikprogrammierung und das Verständnis Algorithmen im Allgemeinen. Es ist eines der nützlichsten Lektionen, die Sie von CS-Studien im Vergleich zu bekommen, was man im allgemeinen Selbststudium sonst.

Answer 4

Computer sind nicht klug, werden sie alles tun, was Sie anweisen, sie zu tun. Compiler kann Code optimieren etwas für Sie, aber sie können nicht Algorithmen optimieren. Das menschliche Gehirn funktioniert anders und das ist, warum Sie die Big O. verstehen müssen, Betrachten der Berechnung Fibonacci-Zahlen. Wir alle wissen, F (n) = F (n-1) + F (n-2), beginnend mit 1,1 Sie können folgende Zahlen leicht ausrechnen, ohne viel Aufwand, in linearer Zeit. Aber wenn Sie Computer sagen, dass es mit dieser Formel zu berechnen (rekursiv), wäre es nicht linear sein (zumindest in imperativen Sprachen). Irgendwie unser Gehirn Algorithmus optimiert, aber Compiler kann dies nicht tun. So haben Sie auf Arbeit auf Algorithmus , um es besser zu machen.

Und dann müssen Sie mit dem Training, Gehirn Optimierungen zu erkennen, die so offensichtlich schauen, um zu sehen, wenn der Code unwirksam sein könnte, zu wissen, Muster für schlechte und gute Algorithmen (in Bezug auf die Rechenkomplexität) und so weiter. Grundsätzlich dienen diese Kurse mehrere Dinge:

• verstehen Hinrichtungs Muster und Datenstrukturen und welche Auswirkungen sie auf die Zeit, um Ihr Programm beenden muss;
• Ihr Gehirn trainiert potenzielle Probleme in Algorithmus zu erkennen, wenn es ineffizient auf große Datenmengen sein könnte. verstehen oder die Ergebnisse der Profilerstellung;
• lernen bekannte Wege Algorithmen zu verbessern, indem sie ihre Rechenkomplexität zu reduzieren;
• bereiten Sie sich ein Interview in der kühlen Firma weitergeben müssen:)

Answer 5

Es ist extrem wichtig. Wenn Sie nicht verstehen, wie aus abzuschätzen und herauszufinden, wie lange Ihre Algorithmen laufen nehmen, dann werden Sie ein paar ziemlich langsam das Schreiben von Code am Ende. Ich denke über das Büro für Komplexität ganze Zeit, wenn Algorithmen zu schreiben. Es ist etwas, das immer auf Ihrem Verstand sein sollte bei der Programmierung.

Dies gilt insbesondere in vielen Fällen, weil, während der App auf Ihrem Desktop-Computer mit einem kleinen Testdatensatz gut funktionieren können, ist es wichtig zu verstehen, wie schnell Ihre Anwendung reagiert, wenn Sie mit ihnen leben zu gehen, und es gibt Hunderte von tausende von Menschen es zu benutzen.

Answer 6

Ja, ich verwende häufig Big-O-Notation, oder besser gesagt, verwende ich die Denkprozesse hinter sich, nicht die Notation selbst. Vor allem, weil so wenige Entwickler in der Organisation (en) Ich verstehe es häufig. Damit meine ich nicht zu den Menschen, respektlos zu sein, aber in meiner Erfahrung, das Wissen von diesem Zeug ist eines dieser Dinge, dass „die Männer von den Jungen sortiert“.

Ich frage mich, ob dies eine jener Fragen, die nur mit „Ja“ beantwortet werden kann? Es scheint mir, dass die Menge der Menschen, die Rechenkomplexität zu verstehen, die Menge der Menschen entspricht in etwa, dass es wichtig ist zu denken. Also, alle, die Antwort könnte nicht vielleicht die Frage nicht verstehen und deshalb würden überspringen auf die nächste Frage, anstatt Pause zu reagieren. Nur ein Gedanke; -)

Answer 7

Es gibt Zeitpunkte, wenn Sie mit Problemen konfrontiert werden, die über sie erfordern denken. Es gibt viele Probleme der realen Welt, die Manipulation von großen Menge von Daten benötigen ...

Beispiele sind:

• Maps-Anwendung ... wie Google Maps - wie würden Sie die Straße Liniendaten weltweit verarbeiten und zeichnen? und Sie müssen sie schnell ziehen!
• Logistik-Anwendung ... denken Verkäufe Mann auf Steroiden reisen
• Data Mining ... alle großen Unternehmen erfordert ein, wie würden Sie eine Datenbank mit 100 Tabellen Mine und 10m + Reihen und kommen mit nützlichen Ergebnisse, bevor die Trends veralten?

einen Kurs in der Rechenkomplexität verwenden, können Sie helfen bei der Analyse und Auswahl / Erstellung von Algorithmen, die für solche Szenarien effizient sind.

Glauben Sie mich, etwas so Einfach wie ein Koeffizienten zu reduzieren, etwa von T (3N) bis T (2n) kann einen großen Unterschiede machen, wenn die „n“ in Tagen gemessen wird, wenn nicht Monate.

Answer 8

Es gibt viele gute Ratschläge hier, und ich bin sicher, dass die meisten Programmierer ihre Komplexität Wissen einmal in eine Weile verwendet haben.

Allerdings soll ich sagen Verständnis Rechenkomplexität von extremer Bedeutung ist im Bereich der Spiele! Ja, Sie davon gehört, dass „nutzlos“ Sachen der Art von Sachen Spiele-Programmierung ist lebt.

würde ich wetten, nur sehr wenige Fachleute kümmern wahrscheinlich über das Big-O so viel wie Spieleprogrammierer.

Answer 9

Ich benutze regelmäßig Komplexität Berechnungen, vor allem weil ich mit sehr großen Datenmengen in der Geospatial-Domäne arbeiten, z.B. Prozesse Millionen und gelegentlich Milliarden von kartesischen Koordinaten beteiligt sind. Sobald Sie mehrdimensionale Probleme beginnen aufbrauchen, kann Komplexität ein echtes Problem, wie gierige Algorithmen, die O (n) in einer Dimension wären plötzlich O-Hop (n ^ 3) in drei Dimensionen und es braucht nicht viele Daten zu einen ernsthaften Engpass erstellen. Wie ich in href="https://stackoverflow.com/questions/133008/what-is-big-o-notation-do-you-use-it#143916">, Sie sehen auch O-Notation unübersichtlich werden, wenn Sie mit Gruppen von komplexen Objekten unterschiedlicher Größe beginnen zu tun. Die Reihenfolge der Komplexität kann auch sehr datenabhängig, mit typischen Fällen der Durchführung viel besser als allgemeine Fälle für gut gestaltete ad hoc Algorithmen.

Es ist auch wert Ihre Algorithmen unter einem Profiler zu testen, um zu sehen ob das, was Sie entworfen haben, ist, was Sie erreicht haben. Ich finde die meisten Engpässe behoben sind viel besser mit Algorithmus Zwicken als verbesserte Prozessorgeschwindigkeit für alle offensichtlichen Gründen.

Für weitere Lesung über die allgemeinen Algorithmen und die Komplexität gefunden Sedgewicks arbeiten sowohl informativ und zugänglich. Für räumliche Algorithmen, O'Rourkes Buch über algorithmische Geometrie ist ausgezeichnet.

Answer 10

In Ihrem normalen Leben, nicht in der Nähe eines Computers sollten Sie Konzepte der Komplexität und Parallelverarbeitung anzuwenden. Dies ermöglicht es Ihnen, effizienter zu sein. Cache-Kohärenz. Dergleichen.

Answer 11

Ja, kam mein Wissen über Sortieralgorithmen in handlichem einem Tag, wenn ich einen Stapel von Studenten Prüfungen zu sortieren hatte. Ich benutzte Mergesort (aber nicht QuickSort oder Heapsort). Bei der Programmierung beschäftige ich nur, was das Sortieren der Bibliothek Angebote Routine. (Noch nicht sortieren wirklich große Menge an Daten hatte.)

ich Komplexitätstheorie nutze die ganze Zeit in der Programmierung, vor allem bei der Entscheidung, welche Datenstrukturen zu verwenden, sondern auch in bei der Entscheidung, ob oder wann die Dinge zu sortieren, und für viele andere Entscheidungen.

Answer 12

Ja "und" nicht

Ja ) Ich verwende häufig große O-Notation wenn Entwicklung und Implementierung von Algorithmen. Z.B. wenn Sie 10 ^ 3 Elemente und Komplexität des ersten Algorithmus O behandeln sollte (n log (n)) und des zweiten O (n ^ 3) ist, können Sie einfach sagen, dass erste Algorithmus nahezu in Echtzeit ist, während der zweite erfordern erhebliche Berechnungen.

Manchmal Kenntnisse über NP Komplexitäten Klassen nützlich sein können. Es kann Ihnen helfen, zu erkennen, dass Sie effizienter Algorithmus darüber nachzudenken, zu erfinden, stoppen, wenn einige NP-vollständiges Problem auf das Problem reduziert werden kann, Sie denken.

nicht ) Was ich oben beschrieben, ist ein kleiner Teil der komplexen Theorie. Als Ergebnis ist es schwierig, zu sagen, dass ich es verwenden, verwende ich Moll-Moll ein Teil davon.

soll ich zugeben, dass es viel Software-Entwicklungsprojekt ist, die nicht die Entwicklung von Algorithmen oder der Verwendung von ihnen in anspruchsvoller Art und Weise berühren. In solchen Fällen ist die Komplexitätstheorie nutzlos. Normale Benutzer von Algorithmen arbeiten häufig Worte mit ‚schnell‘ und ‚langsam‘, "x Sekunden etc.

Answer 13

@ Martin: Können Sie bitte näher auf die Denkprozesse dahinter

ist es vielleicht nicht so explizit wie Hinsetzen und Ausarbeiten der Big-O-Notation für eine Lösung, aber es schafft ein Bewusstsein für das Problem - und das lenkt Sie auf eine effizientere Antwort suchen und von den Problemen in Ansätzen entfernt Sie könnte nehmen. z.B. O (n * n) im Vergleich etwas schneller z.B. Suche nach in einer Liste gespeichert Worten im Vergleich zu in einem Trie (erfundenes Beispiel) gespeichert

Ich finde, dass es einen Unterschied macht, was mit Datenstrukturen I zu verwenden, wählen werde, und wie ich auf eine große Anzahl von Datensätzen arbeiten werden.

Answer 14

Ein gutes Beispiel dafür könnte sein, wenn Ihr Chef Ihnen sagt, irgendein Programm zu tun, und Sie können das, was mit Hilfe der Komplexitätstheorie zeigen Ihr Chef Sie bittet möglich zu tun ist, nicht.