Java時間計算のアルゴリズムと最適化方法の詳細説明

コンピューターの使用経験が増えるにつれて、コンピューターを使用してプログラムを作成するときに必ず次のような質問をするようになります:

プログラムの実行にはどのくらい時間がかかりますか?
コードを最適化して、より高速かつスペース効率を高めることはできますか?

Web ページを開いたり、ファイルを転送したり、プレーヤーを開いたりするときに、上記の質問を自問したことがあるはずです。しかし、この場合の時間とデータ処理の複雑さを見積もるのは非常に難しく、曖昧です。この大規模なアプリケーションと比較すると、私たちが処理できるのは単一プログラムの複雑さと効率です。各プログラムの効率が比較的良好であれば、最終的に結合されたアプリケーションが肥大化して遅くなるのではないかと心配する必要はありません。この記事では、プログラムのアルゴリズムの時空間の複雑さ、最適化方法、その他すべての些細な事項について説明し、3-sum と 2-sum の 2 つの例から始めて、アルゴリズムがプログラムでどのように機能するかを最初から最後まで説明します。 。

例: 3-sum と 2-sum の計算

---

3-sum
ファイル内には繰り返しのない整数がたくさんあります。任意の 3 つの整数でグループを形成でき、その 3 つの整数の合計が 0 になるグループの数を数えます。 2-sum

ファイル内に繰り返しのない整数が多数あります。 の合計が 0 となる整数のペア の数を数えます。
総当りアルゴリズム (従来の最適化されていないアルゴリズム):

  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>

コスト

モデル

このプログラムを最適化したい場合、まずこのプログラムの最適化ポイントがどこにあるかを知る必要があります。これが

評価コストです。モデル

---

。私たちが研究するアルゴリズムの基本的な操作は、プログラムのコスト モデルを決定することによって定義されます。

3-sum問題のコストモデル

3-sum問題を解くアルゴリズムを検討する際、記録するのは配列へのアクセス数
(読み書きに関わらず配列へのアクセス数)つまり目標です。より良いコストモデルを評価するために最善を尽くすことです。 3-sum 問題のモデルは比較的単純ですが、一部の複雑なプログラムのコスト モデルは慎重に決定する必要があります。これは、一部の演算を無視すると、最終的な最適化結果がプログラム全体の最適な状況にならない可能性があるためです。

コストモデルに基づいてプログラムを最適化します

上記の暴力的なコードは結果に問題はなく、データが少ない場合でも実行が遅くなりすぎることはありません。しかし、テスト データの量が 10 の n 乗である場合、この最適化されていないコードは時間に大きな悪影響を及ぼします。暴力的なコードは遅いと言われますが、どのようなコードが速いのでしょうか?

3 合計コスト モデルで、配列アクセスの数が調査および最適化の対象であると判断しました。 Java では、配列へのアクセスにかかる時間は

---

定数

レベルです (定数レベルとは、ほとんど時間がかからないことを意味します)。したがって、配列の内容にアクセスする時間が固定されている場合、配列へのアクセス数を減らすには、コードの実行時間を短縮するだけで済みます。コードを高速化するには、まず分類と時間の計算量が桁違いに増加するという概念を理解する必要があります。

大きさ/時間計算量の増加

これから言おうとしているのは時間計算量ですが、その名前を - 大きさの増加 に変更しました。大きな○マークを使用しないことを除けば、その他の箇所では両者に違いはありません。アルゴリズムを実装する際には、通常のステートメント、ループ

、

---

条件判断

、ネストされたステートメントなど、いくつかの構造プリミティブを使用するため、コスト増加の大きさは一般的に問題サイズ N ある になります。の機能。この例の問題サイズ N は、配列内の数値の数です。 成長順序/時間計算量は主に7種類あります:

一定レベル

成長順序: 1

時間計算量: O(1)
典型的なコード: リーリー
構造プリミティブ: 通常のステートメント

例: 2 つの数値を加算する
説明: 実行時間の桁違いの増加は一定であり、プログラムがタスクを完了するのに必要な時間は固定されており、何もする必要はありません。 Nさんと。 Java のほとんどすべての操作には一定の時間がかかります。一定レベルの速度は、これまでの複雑さの中で最も高速です。
対数レベル

増加の次数: logN

時間計算量: O(logN)
典型的なコード:

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的形式。

线性级别

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

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

结构性原语： 一层循环
举例： 找出最大元素
说明： 线性级别稍慢于对数级别，但快于线性对数级别。他的运行时间和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++;

结构性原语：双层循环
举例：检查所有元素对
说明：平方级别的程序一般都是含有两个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++;

结构性原语：三层循环
举例：对数组中的三个数据进行操作
说明：立方级别的代码一般都是三个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;
    }

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

最適化アルゴリズムの最適化に関する注意事項

---

大きな定数

第 1 項の近似では、通常、低レベル項の定数係数を無視しますが、これは間違っている可能性があります。たとえば、関数 2N²+cN を ~ 2N² に近似するとき、c は小さいと仮定します。しかし、c が 10 の非常に高い累乗である可能性がある場合、近似は間違っています。定数が大きくなる可能性があることに注意する必要があります。

間違ったコストモデル

内側のループが決定的な要素であるという仮定は、必ずしも正しいとは限りません。コスト モデルが正しくないと、真の内部ループを取得できなかったり、ループ内の特定のステートメントに十分な注意が払われなかったりして、時間の見積もりに誤差が生じる可能性があります。全体として、コストモデルには改善が必要です。

以上がJava時間計算のアルゴリズムと最適化方法の詳細説明の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。