So bewerten Sie die Qualität eines Algorithmus-häufiges Problem-php.cn

So bewerten Sie die Qualität eines Algorithmus

Zunächst einmal muss dieser Algorithmus korrekt sein

Zweitens sollte ein guter Algorithmus benutzerfreundlich, für Menschen leicht verständlich und kommunizierbar sowie maschinenausführbar sein.

Dieser Algorithmus muss auch robust genug sein, das heißt, wenn die Eingabedaten illegal oder unvernünftig sind, kann er angemessen reagieren oder sie entsprechend verarbeiten.

Schließlich muss er eine hohe und niedrige Effizienz aufweisen Speicheranforderungen.

Das ist die sogenannte Zeitkomplexität und Raumkomplexität

1. Zeitkomplexität

Definition: In der Informatik die Zeit eines Algorithmus Komplexität ist eine Funktion, die die Laufzeit des Algorithmus quantitativ beschreibt. Theoretisch kann die Zeit, die zur Ausführung eines Algorithmus benötigt wird, nur ermittelt werden, wenn Sie Ihr Programm auf die Maschine legen und es ausführen Die von einem Algorithmus benötigte Zeit ist proportional zur Anzahl der Ausführungen der Grundoperationen im Algorithmus

2. Zeitkomplexität Warum sollte man sie nicht anhand der Zeit messen, statt anhand der Häufigkeit, mit der eine grundlegende Anweisung ausgeführt wird?

Die Ausführungszeit des Algorithmus hängt von der spezifischen Software- und Hardwareumgebung ab. Daher kann die zeitliche Komplexität des Algorithmus nicht an der Länge der Ausführungszeit gemessen werden, sondern an der Größenordnung der Anzahl der grundlegenden Anweisungsausführungen.

3. Big-O-Notation der Zeitkomplexität

ist ein mathematisches Symbol, das zur Beschreibung des asymptotischen Verhaltens einer Funktion verwendet wird.

Big-O-Ordnungsmethode Ableitung:
Berechnen Sie die Größenordnung der Anzahl der Ausführungen einer Basisanweisung.
Sie müssen lediglich die Größenordnung der Anzahl der Ausführungen einer Basisanweisung berechnen, was bedeutet, dass die höchste Potenz vorliegt In der Funktion der Anzahl der Ausführungen ist eine Grundaussage garantiert korrekt, d. h. alle Koeffizienten niedrigerer Potenz und höherer Potenz können ignoriert werden. Dies vereinfacht die Algorithmusanalyse und lenkt die Aufmerksamkeit auf den wichtigsten Punkt: die Wachstumsrate.
Wenn der Algorithmus verschachtelte Schleifen enthält, ist die Grundanweisung normalerweise der innerste Schleifenkörper. Wenn der Algorithmus parallele Schleifen enthält, kommt die zeitliche Komplexität der parallelen Schleifen hinzu. Zum Beispiel:

　for (i=1; i<p> Die zeitliche Komplexität der ersten for-Schleife beträgt Ο(n), die zeitliche Komplexität der zweiten for-Schleife beträgt Ο(n2), dann beträgt die zeitliche Komplexität des gesamten Algorithmus Ο(n +n2)=Ο(n2). </p><p><strong> 4. Zeitkomplexität: optimal, durchschnittlich, schlechtester Fall Warum betrachtet man die zeitliche Komplexität im schlimmsten Fall? </strong></p><p> Die Worst-Case-Komplexität ist die maximale Ressource, die von allen möglichen Eingabedaten verbraucht wird. Wenn die Worst-Case-Komplexität unseren Anforderungen entspricht, können wir garantieren, dass sie in allen Fällen funktioniert Problem. </p><p> Bei bestimmten Algorithmen kommt es häufig zum Worst-Case-Szenario. Beispielsweise muss ein Suchalgorithmus häufig einen Wert finden, der nicht existiert. <br>Vielleicht denken Sie, dass die Komplexität eines durchschnittlichen Falles für Sie attraktiver ist, aber es gibt mehrere Probleme mit dem durchschnittlichen Fall. Erstens ist die Berechnung der Worst-Case-Komplexität bei den meisten Algorithmen viel einfacher als der Durchschnittsfall. Zweitens sind die Durchschnitts- und Worst-Case-Komplexität vieler Algorithmen gleich Durchschnitt? Es ist auch unangemessen anzunehmen, dass alle möglichen Eingabedaten die gleiche Eintrittswahrscheinlichkeit haben. Tatsächlich sind die meisten Situationen anders. Und die Verteilungsfunktion der Eingabedaten wissen Sie wahrscheinlich nicht. <br>Es macht keinen Sinn, die Komplexität des Best-Case-Szenarios zu berücksichtigen. </p><p><strong> 5. Wie löst man: die zeitliche Komplexität der binären Suche, der rekursiven Fakultät und des rekursiven Fibonacci? </strong></p><p>Binäre Suche: Die zeitliche Komplexität der Suche durch Origami beträgt O(logN);<br>Rekursive faktorielle Berechnung: Rekursieren Sie die Grundoperation N-mal, um die zeitliche Komplexität von O(N); Rekursives Fibonacci: Die Analyse zeigt, dass die Grundoperation 2<br>N-mal rekursiv ist und die Zeitkomplexität O(2<sup>N);</sup></p><p> beträgt 6. Was ist Raumkomplexität? <strong></strong></p> Die Speicherplatzkomplexität ist ein Maß für die Menge an Speicherplatz, die ein Algorithmus vorübergehend während des Betriebs einnimmt. Die Speicherplatzkomplexität ist nicht die Anzahl der Bytes an Speicherplatz, die das Programm einnimmt, da dies nicht viel Sinn macht Die Raumkomplexität wird anhand der Anzahl der Variablen berechnet. Die Berechnungsregeln für die Raumkomplexität ähneln im Wesentlichen der Zeitkomplexität und werden ebenfalls mit der großen O-asymptotischen Methode ausgedrückt<p><strong>    7.如何求空间复杂度？ 普通函数&递归函数</strong></p><p style="line-height: 2em;">    一个算法的空间复杂度只考虑在运行过程中为局部变量分配的存储空间的大小，它包括为参数表中形参变量分配的存储空间和为在函数体中定义的局部变量分配的存储空间两个部分。若一个算法为 递归算法，其空间复杂度为递归所使用的堆栈空间的大小，它等于一次调用所分配的临时存储空间的大小乘以被调用的次数(即为递归调用的次数加1，这个1表示开始进行的一次非递归调用)。算法的空间复杂度一般也以数量级的形式给出。如当一个算法的空间复杂度为一个常量，即不随被处理数据量n的大小而改变时，可表示为O(1)；当一个算法的空间复杂度与以2为底的n的对数成正比时，可表示为O(log2n)；当一个算法的空间复杂度与n成线性比例关系时，可表示为O(n).若形参为数组，则只需要为它分配一个存储由实参传送来的一个地址指针的空间，即一个机器字长空间；若形参为引用方式，则也只需要为其分配存储一个地址的空间，用它来存储对应实参变量的地址，以便由系统自动引用实参变量。</p><p style="line-height: 2em;"><strong>    8. 分析递归斐波那契数列的：时间、空间复杂度，并对其进行优化，伪递归优化—>循环优化</strong></p><pre class="brush:php;toolbar:false">long long Fib(int N) {
	if (N <p>    普通递归实现的斐波那契数列:<br>    时间复杂度:O(2^n)<br><img src="https://img.php.cn/upload/article/000/000/051/79601e8681a1e563f3ddfcadebcb758c-0.png" alt="So bewerten Sie die Qualität eines Algorithmus"><br>    计算并根据<strong>O渐进表示法</strong>得出时间复杂度.</p><p>    空间复杂度:O(N);递归深度乘以(每一次递归的空间占用{有辅助空间或常量})</p><p>    伪递归优化:</p><pre class="brush:php;toolbar:false">long long fib (long long first, longlong second, int N) {
	if(N <p>    时间复杂度:<br>    O(N);<br>    递归深度乘以每次递归的循环次数<br>    空间复杂度:<br>    O(1)或O(N)<br>    关键看编译器是否优化,优化则为O(1)否则O(N);</p><p>    循环优化:</p><pre class="brush:php;toolbar:false">long long  Fib(int N) {
	long long first = 1;
	long long second = 1;
	long long ret = 0;
	
	for (int i = 3; i <p>    时间复杂度:O(N);</p><p>    空间复杂度:O(1);</p><p>    <strong>9.常见时间复杂度</strong></p><p>    常见的算法时间复杂度由小到大依次为：　　Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜…＜Ο(2n)＜Ο(n!)　　Ο(1)表示基本语句的执行次数是一个常数，一般来说，只要算法中不存在循环语句，其时间复杂度就是Ο(1)。Ο(log2n)、Ο(n)、Ο(nlog2n)、Ο(n2)和Ο(n3)称为多项式时间，而Ο(2n)和Ο(n!)称为指数时间。</p><link href="https://csdnimg.cn/release/phoenix/mdeditor/markdown_views-60ecaf1f42.css" rel="stylesheet"><!-- flowchart 箭头图标 勿删 --><svg xmlns="http://www.w3.org/2000/svg" style="display: none;"><path stroke-linecap="round" d="M5,0 0,2.5 5,5z" id="raphael-marker-block" style="-webkit-tap-highlight-color: rgba(0, 0, 0, 0);"></path></svg>

Nach dem Login kopieren

Das obige ist der detaillierte Inhalt vonSo bewerten Sie die Qualität eines Algorithmus. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!