Wenn jemand über den Big-O eines Algorithmus ohne Qualifikation spricht, beziehen sich diese auf den besten, den durchschnittlichsten oder den schlechtesten laufenden Fall?

Question

Wenn jemand über den Big-O eines Algorithmus ohne Qualifikation spricht, beziehen sich diese auf den besten, den durchschnittlichsten oder den schlechtesten laufenden Fall? Schlüsselwort ist "ohne Qualifikation".

Answer 1

Big-O ist technisch die Obergrenze, also wollen Sie Worst-Case-Analyse.

Es gibt auch und Big-Theta sowie erwarteten Fall (bei Verwendung von Randomisierung), durchschnittlich, usw. Normalerweise, wenn jemand nicht angibt, können Sie einfach die Big-O tun, aber wenn Sie leicht in der Lage sind, mehr zu bieten Info, dann könntest du auch. z.B. Big-Theta gibt Ihnen die Big-O und zusätzliche Informationen. Wenn Sie einen Algorithmus-Kurs belegen und eine Problemanalyse durchführen müssen, sollten Sie mit Ihrem Professor sprechen, um zu sehen, was er erwartet. Mehr als wahrscheinlich, sie sehen, wie viel Sie herausfinden können, also without qualification könnte bedeuten, ihnen zu zeigen, was Sie wissen oder herausfinden können.

Im Zweifelsfall, als die Person, die um die Informationen zur weiteren Klärung bittet. Normalerweise, je mehr Informationen Sie herausfinden können, desto besser. Sie können Stärken von Algorithmen finden, indem Sie weitere Analysen durchführen.

Zum Beispiel ist die Verwendung eines linked list ideal zum Einfügen O(1). Solange Sie nicht nach etwas suchen müssen, könnte es eine wünschenswerte Datenstruktur sein, die in einem Algorithmus verwendet wird. Wenn Ihr Algorithmus viele Suchen durchführen muss, dann ist linked list wahrscheinlich nicht die Datenstruktur, die Sie mit Ihrem Algorithmus verwenden.