Wie kann ich die zeitliche Komplexität eines Methodenaufrufs herausfinden, wenn der Zugriff auf die Quelle hart/nicht möglich ist?

Question

Da OOP recht ordentlich ist, um die Implementierung zu abstrahieren, frage ich mich immer noch, welche Art von Zeit-Komplexität eine bestimmte Operation hat, wenn man sie benutzt.

Beispiel: Dokumentation von Collection.min

/** 
* Returns the minimum element of the given collection, according to the 
* <i>natural ordering</i> of its elements. All elements in the 
* collection must implement the <tt>Comparable</tt> interface. 
* Furthermore, all elements in the collection must be <i>mutually 
* comparable</i> (that is, <tt>e1.compareTo(e2)</tt> must not throw a 
* <tt>ClassCastException</tt> for any elements <tt>e1</tt> and 
* <tt>e2</tt> in the collection).<p> 
* 
* This method iterates over the entire collection, hence it requires 
* time proportional to the size of the collection. 
* 
* @param <T> the class of the objects in the collection 
* @param coll the collection whose minimum element is to be determined. 
* @return the minimum element of the given collection, according 
*   to the <i>natural ordering</i> of its elements. 
* @throws ClassCastException if the collection contains elements that are 
*   not <i>mutually comparable</i> (for example, strings and 
*   integers). 
* @throws NoSuchElementException if the collection is empty. 
* @see Comparable 
*/ 

Dies ist ein triviales Beispiel, da es leicht zu sehen, wenn an der Quelle suchen, aber es wird noch schwieriger, wenn die Umsetzung komplizierter ist oder nicht sichtbar überhaupt .

Meine Frage: Wie kann ich schnell die Zeit-Komplexität bestimmen, um zu entscheiden, ob es sinnvoll ist zu verwenden? Versuch und Fehler? Zeitprotokollierung?

EDIT: Es ist nicht das beste Beispiel, da es auch in der Dokumentation geschrieben ist, aber die Frage bleibt: Was ist, wenn es nicht in Doku geschrieben ist?

Answer 1

Es ist offensichtlich nicht möglich, die Zeitkomplexität einer Black-Box-Funktion zu bestimmen. Komplexität ist eine Worst-Case-Definition. Sie können eine Funktion haben, die in linearer Zeit für die meisten Eingaben läuft, aber explodiert und Millionen von Jahren für 1 von 100 Milliarden Eingaben benötigt. Es gibt keine Möglichkeit, dies auszuschließen. Wenn Sie andererseits eine vernünftige Wahrscheinlichkeitsverteilung für mögliche Eingaben einer gegebenen Größe haben, können Sie statistische Methoden verwenden, um die durchschnittliche Zeitkomplexität für die verschiedenen Größen zu schätzen und dann die Kurvenanpassung zu verwenden eine heuristische Kurve zur Schätzung der durchschnittlichen Laufzeit.

Ein realistisches Beispiel. Die simplex algorithm für die lineare Programmierung läuft in der Praxis sehr schnell. Aber es wurde in den 1970er Jahren (über sehr sorgfältig konstruierte Beispiele) bewiesen, exponentielle Zeitkomplexität zu haben. Nichtsdestotrotz wird der Simplex-Algorithmus wegen seiner schönen durchschnittlichen Zeitkomplexität immer noch stark verwendet. Seitdem wurden Polynomzeitalgorithmen für die lineare Programmierung entdeckt und implementiert. Wenn Sie eine Methode haben, die lineare Programmierprobleme löst, dann gibt es vielleicht keine einfache Möglichkeit zu wissen, ob sie den Exponentialzeit-Simplexalgorithmus oder einen der neueren Polynomzeitalgorithmen implementiert.

(Beachten Sie, dass es möglich sein könnte, eine Funktion zu dekompilieren -. Aber in diesem Fall ist es nicht mehr schwarz-Box)