Mit zunehmender Erfahrung im Umgang mit Computern werden Menschen unweigerlich Fragen wie diese stellen, wenn sie Computer zum Schreiben von Programmen verwenden:

Wie lange dauert es, bis mein Programm ausgeführt wird?
Kann mein Code optimiert werden, um schneller und platzsparender zu sein?

Wenn wir eine Webseite öffnen, eine Datei übertragen oder einen Player öffnen, müssen Sie sich die oben genannten Fragen gestellt haben. Die Schätzung des Zeitaufwands und der Komplexität der Datenverarbeitung ist in diesem Fall jedoch zu schwierig und vage. Im Vergleich zu dieser großen Anwendung können wir die Komplexität und Effizienz eines einzelnen Programms bewältigen. Wenn die Effizienz jedes Programms relativ gut ist, müssen wir uns keine Sorgen machen, dass die endgültige kombinierte Anwendung zu aufgebläht und langsam ist. In diesem Artikel werden die algorithmische Raum-Zeit-Komplexität des Programms, Optimierungsmethoden und alle trivialen Dinge erläutert. Ausgehend von den beiden Beispielen 3-Summe und 2-Summe wird von Anfang bis Ende gezeigt, wie der Algorithmus in unserem Programm funktioniert . .

Beispiel: 3-Summen- und 2-Summen-Berechnung

3-Summen
Es gibt viele sich nicht wiederholende Ganzzahlen in einer Datei. Drei beliebige Ganzzahlen können eine Gruppe bilden. Zählen Sie die Anzahl der Gruppen, in denen die Summe aller drei Ganzzahlen 0 ist.

2-Summe Es gibt viele sich nicht wiederholende Ganzzahlen in einer Datei. Zählen Sie die Anzahl der Ganzzahlpaare
, in denen die Summe von 0 ist.

Brute-Force-Algorithmus (regulärer, nicht optimierter Algorithmus):

  public int threeSum(int[] arr) {
        int count = 0;
        int n = arr.length;
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++)
                for (int k = j + 1; k < n; k++)
                    if (arr[i] + arr[j] + arr[k] == 0)
                        count++;
        return count;
    }

Nach dem Login kopieren

<p style="margin-bottom: 7px;">  public int twoSum(int[] arr) {<br/>        int count = 0;<br/>        int n = arr.length;<br/>        for (int i = 0; i < n; i++)<br/>            for (int j = i + 1; j < n; j++)<br/>                if (arr[i] == -arr[j])<br/>                    count++;<br/>        return count;<br/>    }<br/></p>

Nach dem Login kopieren

KostenModell

Wenn wir dieses Programm optimieren wollen, müssen wir zunächst wissen, wo dieses Programm optimiert werden kann. Dies ist das

Bewertungskostenmodell. Die Grundoperationen in den von uns untersuchten Algorithmen werden durch die Bestimmung des Kostenmodells des Programms definiert.

Kostenmodell für 3-Summen-Problem Bei der Untersuchung des Algorithmus zur Lösung des 3-Summen-Problems erfassen wir die Anzahl der Zugriffe auf das Array
(die Anzahl der Zugriffe auf das Array, unabhängig vom Lesen und Schreiben).

Ersetzen Kurz gesagt: Unser Ziel ist es, das von uns bewertete Kostenmodell so gut wie möglich zu gestalten. Beim 3-Summen-Problem ist das Modell relativ einfach, aber das Kostenmodell einiger komplexer Programme muss sorgfältig bestimmt werden, denn wenn wir einige Operationen ignorieren, ist das endgültige Optimierungsergebnis möglicherweise nicht die optimale Situation des Gesamtprogramms.

Optimieren Sie das Programm basierend auf dem Kostenmodell

Der obige gewalttätige Code hat keine Probleme mit den Ergebnissen und funktioniert dort nicht gut ist weniger Daten. Es ist zu langsam. Wenn die Menge der Testdaten jedoch 10 hoch n-tel beträgt, wird dieser nicht optimierte Code einen großen negativen Einfluss auf die Zeit haben. Wir sagen, dass gewalttätiger Code langsam ist, aber welcher Code ist schnell?

Wir haben festgestellt, dass wir die Anzahl der Zugriffe auf das Array untersuchen und im 3-Summen-Kostenmodell optimieren möchten. In Java ist der Zeitaufwand für den Zugriff auf ein Array

konstant (konstanter Wert bedeutet, dass fast keine Zeit verbraucht wird). Wenn also die Zeit für den Zugriff auf den Inhalt des Arrays festgelegt ist, müssen wir nur die Codelaufzeit verkürzen, um die Anzahl der Zugriffe auf das Array zu verringern. Um Code schneller zu machen, müssen wir zunächst die Konzepte der Klassifizierung und der Zeitkomplexität verstehen, die um Größenordnungen zunehmen.

Ordnung des Wachstums/Zeitkomplexität

Worüber wir sprechen werden, ist Zeitkomplexität, aber wir haben ihr einen anderen Namen gegeben – Ordnung des Wachstums. Abgesehen davon, dass das große O-Zeichen nicht verwendet wird, gibt es an anderen Stellen keinen Unterschied zwischen den beiden. Bei der Implementierung des Algorithmus haben wir mehrere

Strukturprimitive verwendet, z. B. gewöhnliche Anweisungen, Schleifen, bedingte Urteile, verschachtelte Anweisungen usw. Die Größenordnung von Kostenwachstum ist im Allgemeinen eine Funktion der Problemgröße N. Die Problemgröße N ist in diesem Beispiel die Anzahl der Zahlen im Array. Es gibt sieben Haupttypen der Größenordnung/Zeitkomplexität:

Konstantes Niveau

Ordnung von Ausmaß des Wachstums:

1 Zeitkomplexität:
O(1) Typischer Code:

a = b + c;

Nach dem Login kopieren

Strukturprimitiv :

Allgemeine AussageBeispiel:
Addiere zwei ZahlenErklärung:
Die Größenordnung der Erhöhung der Laufzeit ist das, was ein Programm mit konstantem Niveau benötigt, um seine Laufzeit abzuschließen Die Aufgabenzeit ist fest und hat nichts mit N zu tun. Fast alle Operationen in Java benötigen eine konstante Zeit. Eine konstante Geschwindigkeit ist die schnellste aller Zeitkomplexität.

Log-Level

Wachstumsordnung:

logN Zeitkomplexität:
O (logN) Typischer Code:

public static int rank(int key, int[] a, int lo, int hi) {
        if (hi < lo)
            return -1;
        int mi = lo + (hi - lo) / 2;
        if (key < a[mi])
            return rank(key, a, lo, mi - 1);
        else if (key > a[mi])
            return rank(key, a, mi + 1, hi);
        else
            return mi;
    }

Nach dem Login kopieren

结构性原语：二分策略
举例：二分查找
说明：速度稍微慢于常数级别，但快于O(N)最典型的对数级别的例子就是二分查找，log下面的底数可能是变化的，但是因为只是一个常数对整体和N的影响不大，所以我们一般表示成logN的形式。

线性级别

增长的数量级： N
时间复杂度： O(N)
典型代码：

for (int i = 0; i < n; i++)
        if(arr[i] == 0)
            count++;

Nach dem Login kopieren

结构性原语： 一层循环
举例： 找出最大元素
说明： 线性级别稍慢于对数级别，但快于线性对数级别。他的运行时间和N成正比。在有些情况下，我们只需要进行一半的数组遍历，理论上可以将时间除以2，但是仍旧与N的一次方有关，所以我们把此类都算作线性级别。

线性对数级别

增长的数量级： NlogN
时间复杂度： O(NlogN)
典型代码：
归并排序
结构性原语： 分治
举例： 归并排序
说明： 线性N乘以对数logN，速度快于N²但是慢于线性级别。在归并排序中，按照类似二分的方法确定归并点，对归并到最底层的数据进行复杂度为O(N)的排序，时间复杂度为O(NlogN)。快速排序，归并排序都可以看作是线性对数级别。

平方级别

增长的数量级： N²
时间复杂度： O(N²)
典型代码：

for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++)
                if (arr[i] == -arr[j])
                    count++;

Nach dem Login kopieren

结构性原语：双层循环
举例：检查所有元素对
说明：平方级别的程序一般都是含有两个for循环，初级的排序算法选择排序和插入排序都是这种复杂度。

立方级别

增长的数量级： N³
时间复杂度： O(N³)
典型代码：

for (int i = 0; i < n; i++)  for (int j = i + 1; j < n; j++)
        for (int k = j + 1; k < n; k++)
            if (arr[i] + arr[j] + arr[k] == 0)
                count++;

Nach dem Login kopieren

结构性原语：三层循环
举例：对数组中的三个数据进行操作
说明：立方级别的代码一般都是三个for循环嵌套而成，我们日常的算法很少有这种运算时长。

指数级别

增长的数量级： 2^N
时间复杂度： O(2^N)
典型代码：
穷举查找所有真子集
结构性原语：穷举法
举例：穷举查找所有真子集
说明：指数级别的增长在N较大时比较可怕，但是它确是某些问题看起来最优的解法，并不是很常用，等如果需要学习的时候可以专门研究。

优化2-sum问题

先从2-sum问题入手，根据上述复杂度，2-sum问题的暴力解法复杂度为O(N²)，又根据我们的成本模型只考虑访问数组次数，所以我们要在O(N²)的复杂度之内寻求最优解法即可。

从上面得知，排序算法的复杂度是O(NlogN)快于O(N²)，而我们对排序之后的数据进行运算时，已经不是在排序内部进行处理。所以最后计算时间是用加法而不是乘法。所以我们最后的解决策略是：我们先对整个数组进行排序，然后从数组头部依次读取a[i]，在数组中检索是否存在-a[i]。这种检索采用了二分查找的方法，复杂度为O(logN)。为了避免重复查找，如果查找到-a[i]的位置在a[i]之前，就说明该元素对已经被查找过，不计入次数。这样整体的算法复杂度是NlogN+N*logN（不知道这样写是否规范）。两项合并系数忽略，所以最后算法整体的复杂度为O(NlogN)。

public int twoSum(int[] arr) {
        int count = 0;
        Arrays.sort(arr);
        for (int i = 0; i < arr.length; i++)
            if (Arrays.binarySearch(arr, -arr[i]) > i)
                count++;
        return count;
    }

Nach dem Login kopieren

2-sum问题已经成功的进行了优化，3-sum问题也可以通过这种方式进行优化，但是最后优化的复杂度为O(N²logN)，感兴趣的朋友可以自己试一试，或者有更简便算法的话，发在评论里我们交流一下。不胜感激。

Hinweise zur Optimierung von Optimierungsalgorithmen

Große Konstante

In der ersten Termnäherung Wir Im Allgemeinen werden konstante Koeffizienten auf niedriger Ebene ignoriert, dies kann jedoch falsch sein. Wenn wir beispielsweise die Funktion 2N²+cN an ~ 2N² annähern, gehen wir davon aus, dass c klein ist. Wenn c jedoch eine sehr hohe Zehnerpotenz sein könnte, ist die Näherung falsch. Wir müssen auf Konstanten achten, die groß sein können.

Falsches Kostenmodell

Die Annahme, dass die innere Schleife der entscheidende Faktor ist, ist nicht immer richtig. Ein falsches Kostenmodell kann möglicherweise nicht die wahre innere Schleife ermitteln oder bestimmte Anweisungen in der Schleife nicht ausreichend berücksichtigen, was zu Fehlern bei der Zeitschätzung führt. Insgesamt ist das Kostenmodell verbesserungswürdig.

Das obige ist der detaillierte Inhalt vonAusführliche Erläuterung von Algorithmen und Optimierungsmethoden zur Java-Zeitberechnung. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!