Entschuldigung für die Frage des Neulings, aber ich bin etwas verwirrt darüber, was genau als "einfache Operation" gilt, wenn ich die zeitliche Komplexität eines Algorithmus erarbeite. Warum betrachten wir insbesondere alle Operationen als gleich?
Das Teilen von zwei sehr großen Zahlen ist sicherlich zeitaufwändiger als das Hinzufügen einer zu einer Zahl (wie bei jeder Iteration einer for-Schleife). Die Multiplikation kann beispielsweise aus einer beliebigen Anzahl kleiner Additionen bestehen. Sollten wir nicht statt nur eine Addition auf jede Operation anwenden, abhängig von der Art der Operation (Addition, Multiplikation usw.) und der Größe der beteiligten Zahlen?
Mein Problem ist, dass ich aufgefordert werde zu beweisen, dass die Komplexität meines Algorithmus (für einige Funktionen f ), und ich bin mir nicht sicher, wie ich dies auf mathematisch strenge Weise tun soll, da die Definition von vage ist eine "einfache Operation". Wie würde ich das machen?
quelle
Antworten:
Einfache Operationen sind alles, was konstante Zeit in Anspruch nimmt. Die Verwirrung ist, dass die Teilung keine konstante Zeit in Anspruch zu nehmen scheint, und im Allgemeinen auch nicht. ABER!
Division und Addition nehmen beide eine konstante Zeit in Anspruch, wenn Sie beispielsweise zwei 32-Bit-Ganzzahlen addieren, wie dies normalerweise der Fall ist. Wenn Sie jedoch beliebig große Zahlen hinzufügen, sind diese nicht wirklich zeitkonstant, obwohl ich manchmal denke, dass die Leute sie so behandeln, als ob es daran liegt, dass die Zahlen sozusagen nicht sehr groß werden.
quelle