Explication détaillée des algorithmes et des méthodes d'optimisation pour le calcul du temps Java

À mesure que l'expérience de l'utilisation des ordinateurs augmente, les gens poseront inévitablement des questions comme celle-ci lorsqu'ils utilisent des ordinateurs pour écrire des programmes :

Combien de temps faut-il pour que mon programme s'exécute ?
Mon code peut-il être optimisé pour être plus rapide et plus efficace en termes d'espace ?

Lorsque nous ouvrons une page Web, transférons un fichier ou ouvrons un lecteur, vous devez vous être posé les questions ci-dessus. Mais estimer le temps et la complexité du traitement des données dans ce cas est trop difficile et vague. Par rapport à cette grande application, ce que nous pouvons gérer, c'est la complexité et l'efficacité d'un seul programme. Si l'efficacité de chaque programme est relativement bonne, nous n'avons pas à craindre que l'application finale combinée soit trop lourde et trop lente. Cet article expliquera la complexité spatio-temporelle algorithmique du programme, les méthodes d'optimisation et toutes les questions triviales. À partir des deux exemples de 3-somme et 2-somme, il démontrera du début à la fin comment l'algorithme fonctionne sur notre programme. .

Exemple : calcul à 3 sommes et à 2 sommes

---

3 sommes
Il existe de nombreux entiers non répétitifs dans un fichier. Trois entiers peuvent former un groupe dans lesquels la somme de trois entiers est égale à 0.

2 sommes Il existe de nombreux entiers non répétitifs dans un fichier. Comptez le nombre de paires d'entiers
dans lesquelles la somme de est 0.

Algorithme de force brute (algorithme régulier non optimisé) :

  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>

CoûtModèle

---

Si l'on veut optimiser ce programme, il faut d'abord savoir où ce programme peut être optimisé. C'est le

modèle de coût d'évaluation. Les opérations de base des algorithmes que nous étudions sont définies en déterminant le modèle de coût du programme.

Modèle de coût pour un problème à 3 sommes Lors de l'étude de l'algorithme pour résoudre le problème à 3 sommes, ce que nous enregistrons est le nombre d'accès au
tableau (le nombre d'accès au tableau, indépendamment de la lecture et de l'écriture)

Remplacer En bref, notre objectif est de rendre le modèle de coûts que nous évaluons aussi bon que possible. Le modèle du problème à 3 sommes est relativement simple, mais le modèle de coût de certains programmes complexes doit être déterminé avec soin, car si nous ignorons certaines opérations, le résultat final de l'optimisation peut ne pas être la situation optimale de l'ensemble du programme.

Optimiser le programme en fonction du modèle de coût

---

Le code violent ci-dessus n'a aucun problème avec les résultats, et il ne fonctionne pas bien quand il y a c'est moins de données. C'est trop lent. Mais si la quantité de données de test est de 10 à la puissance n, alors ce code non optimisé aura un impact négatif important sur le temps. Nous disons que le code violent est lent, mais quel type de code est rapide ?

Nous avons déterminé que le nombre d'accès au tableau est ce que nous voulons étudier et optimiser dans le modèle de coût à 3 sommes. En Java, le temps consommé pour accéder à un tableau est de niveau

constant (un niveau constant signifie qu'il ne consomme presque pas de temps). Ainsi, lorsque le temps d'accès au contenu du tableau est fixé, pour réduire le nombre d'accès au tableau, il suffit d'accélérer le temps d'exécution du code. Afin de rendre le code plus rapide, nous devons d’abord comprendre les concepts de classification et de complexité temporelle qui augmentent par ordres de grandeur.

Ordre de croissance/complexité temporelle

---

Ce dont nous allons parler est de la complexité temporelle, mais nous lui avons donné un nom différent - Ordre de croissance. À part ne pas utiliser la grande marque O, il n'y a aucune différence entre les deux ailleurs. Nous avons utilisé plusieurs

primitives structurelles lors de l'implémentation de l'algorithme, telles que des instructions ordinaires, des boucles, des jugements conditionnels, des instructions imbriquées, etc., donc l'ordre de grandeur de la croissance des coûts est généralement une fonction de la taille du problème N. La taille du problème N dans cet exemple est le nombre de nombres dans le tableau. Il existe sept principaux types d'ordre de grandeur/complexité temporelle :

Niveau constant

Ordre de ampleur de la croissance :

1 Complexité temporelle :
O(1) Code typique :

a = b + c;

Primitive structurelle :

Déclaration communeExemple :
Ajouter deux nombresExplication :
L'augmentation de l'ordre de grandeur du temps d'exécution est ce dont un programme de niveau constant a besoin pour terminer son Le temps de la tâche est fixe et n'a rien à voir avec N. Presque toutes les opérations en Java prennent un temps constant. La vitesse à niveau constant est la plus rapide de toutes les complexités temporelles.

Niveau de journal

Ordre de croissance :

logN Complexité temporelle :
O (logN) Code typique :

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)，感兴趣的朋友可以自己试一试，或者有更简便算法的话，发在评论里我们交流一下。不胜感激。

Notes sur l'optimisation des algorithmes d'optimisation

---

Grande constante

Dans l'approximation du premier terme, nous ignorent généralement les coefficients constants en termes de bas niveau, mais cela peut être erroné. Par exemple, lorsque nous approchons la fonction 2N²+cN de ~ 2N², notre hypothèse est que c est petit. Mais si c peut être une puissance très élevée de 10, l’approximation est fausse. Nous devons être sensibles aux constantes qui peuvent être importantes.

Mauvais modèle de coût

L'hypothèse selon laquelle la boucle interne est le facteur décisif n'est pas toujours correcte. Un modèle de coût incorrect peut ne pas parvenir à obtenir la véritable boucle interne ou ne pas accorder suffisamment d’attention à certaines déclarations de la boucle, ce qui entraîne des erreurs d’estimation du temps. Dans l’ensemble, le modèle de coûts doit être amélioré.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!