Algorithmen und Datenstrukturen · Junior · Frage 4 von 75
Warum schreibt man O(2n + 10) einfach als O(n)?
- 1Weil der Compiler den konstanten Faktor wegoptimiert
- 2Weil Konstanten und Terme niedrigerer Ordnung die Wachstumsrate nicht ändern
- 3Weil die O-Notation nur für gerade Zahlen von Operationen gilt
Antwort zeigen
Richtige Antwort: Weil Konstanten und Terme niedrigerer Ordnung die Wachstumsrate nicht ändern
Erklärung
Die O-Notation beschreibt die Form des Wachstums für großes n. Mal 2 oder plus 10 ändert nichts daran, dass die Kosten linear wachsen, daher fallen beide weg. In der Praxis zählen Konstanten trotzdem, deshalb gibt es Benchmarks.