Ist die Variable Initialisierung/Zuweisungsanweisung eine einzelne Operation oder mehr?

Question

Ich lerne gerade über die Performance-Analyse des Algorithmus

meine Frage: ist int i=0; wird als zwei Operation gezählt: assisgment, Initialisierung oder es ist nur eine kompakte Operation? Ich benutze asymptotische Analyse, die die Anzahl der Operationen als ein Beispiel verwendet, um die Leistung zu beschreiben

Answer 1

Es gibt keine einzige richtige Antwort darauf.

In einigen Kontexten können Menschen eine einzelne arithmetische Operation als "eine" Operation analysieren. Zu anderen Zeiten können sie sehr genau interessieren, wie viele Zyklen eine Operation dauern wird, und sie möchten vielleicht sagen, dass z.B. Das Hinzufügen von Ints ist billiger als das Multiplizieren von Floats. In vielen Kontexten sagen Programmierer, dass die Dereferenzierung eines Zeigers O(1) ist. Jedoch, wenn Sie wirklich den Fall betrachten, wenn n ins Unendliche geht, wenn Ihre n ist wie die Größe des Universums, macht es noch Sinn zu sagen, dass Dereferenzierung eines Zeigers in das ist O(1) Operation? In some theoretical contexts, werden Leute sagen, dass Dereferenzierung eines Zeigers im Wesentlichen O(log n) ist.

Allerdings sprach ich einmal mit einem Physiker, der sagte, dass sogar O(log n) möglicherweise nicht physikalisch realistisch ist - er sagt, dass es eine maximale Informationsdichte gibt, die das Universum in einem gegebenen Volumenraum haben kann. Dies nennt man "Bekenstein Bound", es stellt sich heraus, dass die maximale Entropie durch ein schwarzes Loch erreicht wird. Wenn Sie annehmen, dass in einem Raumvolumen n Sie nur O(n) Speicherbits haben können, bedeutet es im Grunde, dass in einem galaktisch großen Computer Bits wie Bälle in sphere packing problem verpackt werden müssen, und dann der Abstand zwischen einem typischen Paar von Bits wächst als O(n^{1/3}). Da Informationen nicht schneller als Lichtgeschwindigkeit gehen ... braucht die Dereferenzierung eines Zeigers O(n^{1/3}) asymptotisch? O.o

Punkt ist, dies nicht überdenken. Alles, was Sie in der asymptotischen Analyse tun, ist letztlich eine Annäherung, Sie versuchen nur, eine nützliche Vorstellung davon zu bekommen, wie lange es dauern wird. Dinge, die Sie ziemlich sicher sind, werden in Ihrem Fall nicht wirklich wichtig sein, können Sie als O(1) analysieren, um sich auf die Dinge zu konzentrieren, die wichtig sind. In einer anderen Situation können Sie dieselben Dinge auch anders analysieren, wenn sie das "meiste" der Arbeit darstellen.

IMO Wenn Sie wissen möchten, wie Sie Fragen zu diesem Thema in einem Vorstellungsgespräch beantworten, sollten Sie bereit sein, es auf verschiedene Arten zu analysieren, und zeigen Sie, dass Sie verstehen, dass Dinge wie "does int i = 0; zählen als eine Operation oder zwei "sind im Grunde eine Konvention.