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 . .
Brute-Force-Algorithmus (regulärer, nicht optimierter Algorithmus):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.
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;
}<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>Bewertungskostenmodell. Die Grundoperationen in den von uns untersuchten Algorithmen werden durch die Bestimmung des Kostenmodells des Programms definiert.
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.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).
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:
1 Zeitkomplexität:
O(1) Typischer Code:
a = b + c;
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.
logN Zeitkomplexität: 结构性原语：二分策略 增长的数量级： N 结构性原语： 一层循环 增长的数量级： NlogN 增长的数量级： N2 结构性原语：双层循环 增长的数量级： N3 结构性原语：三层循环 增长的数量级： 2N 先从2-sum问题入手，根据上述复杂度，2-sum问题的暴力解法复杂度为O(N2)，又根据我们的成本模型只考虑访问数组次数，所以我们要在O(N2)的复杂度之内寻求最优解法即可。 从上面得知，排序算法的复杂度是O(NlogN)快于O(N2)，而我们对排序之后的数据进行运算时，已经不是在排序内部进行处理。所以最后计算时间是用加法而不是乘法。所以我们最后的解决策略是：我们先对整个数组进行排序，然后从数组头部依次读取a[i]，在数组中检索是否存在-a[i]。这种检索采用了二分查找的方法，复杂度为O(logN)。为了避免重复查找，如果查找到-a[i]的位置在a[i]之前，就说明该元素对已经被查找过，不计入次数。这样整体的算法复杂度是NlogN+N*logN（不知道这样写是否规范）。两项合并系数忽略，所以最后算法整体的复杂度为O(NlogN)。 2-sum问题已经成功的进行了优化，3-sum问题也可以通过这种方式进行优化，但是最后优化的复杂度为O(N2logN)，感兴趣的朋友可以自己试一试，或者有更简便算法的话，发在评论里我们交流一下。不胜感激。 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 2N2+cN an ~ 2N2 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. 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!
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;
}
举例：二分查找
说明：速度稍微慢于常数级别，但快于O(N)最典型的对数级别的例子就是二分查找，log下面的底数可能是变化的，但是因为只是一个常数对整体和N的影响不大，所以我们一般表示成logN的形式。线性级别
时间复杂度： O(N)
典型代码： for (int i = 0; i < n; i++)
if(arr[i] == 0)
count++;
举例： 找出最大元素
说明： 线性级别稍慢于对数级别，但快于线性对数级别。他的运行时间和N成正比。在有些情况下，我们只需要进行一半的数组遍历，理论上可以将时间除以2，但是仍旧与N的一次方有关，所以我们把此类都算作线性级别。线性对数级别
时间复杂度： O(NlogN)
典型代码：
归并排序
结构性原语： 分治
举例： 归并排序
说明： 线性N乘以对数logN，速度快于N2但是慢于线性级别。在归并排序中，按照类似二分的方法确定归并点，对归并到最底层的数据进行复杂度为O(N)的排序，时间复杂度为O(NlogN)。快速排序，归并排序都可以看作是线性对数级别。平方级别
时间复杂度： O(N2)
典型代码：for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if (arr[i] == -arr[j])
count++;
举例：检查所有元素对
说明：平方级别的程序一般都是含有两个for循环，初级的排序算法选择排序和插入排序都是这种复杂度。立方级别
时间复杂度： O(N3)
典型代码：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++;
举例：对数组中的三个数据进行操作
说明：立方级别的代码一般都是三个for循环嵌套而成，我们日常的算法很少有这种运算时长。指数级别
时间复杂度： O(2N)
典型代码：
穷举查找所有真子集
结构性原语：穷举法
举例：穷举查找所有真子集
说明：指数级别的增长在N较大时比较可怕，但是它确是某些问题看起来最优的解法，并不是很常用，等如果需要学习的时候可以专门研究。优化2-sum问题
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;
}Hinweise zur Optimierung von Optimierungsalgorithmen
Große Konstante
Falsches Kostenmodell
