Le Kième facteur de N - un algorithme O(sqrt n)

Introduction

Récemment, j'ai écrit l'article Apprenez la notation Big O une fois pour toutes. Dans cet article, je passe en revue tous les types de notation temporelle Big O disponibles sur l'aide-mémoire Big-O. Et je ne pensais pas qu’il y aurait d’autres notations temporelles possibles en dehors de ces sept.

Comme si l'univers lui-même m'humiliait et se moquait de mon ignorance, j'ai rencontré un problème LeetCode avec une solution de O(√n) temps. Ce qui pourrait se traduire par O(N^1/2), si vous êtes fou.

Le problème

Vous recevez deux entiers positifs n et k. Un facteur d'un entier n est défini comme un entier i où n % i == 0.

Considérons une liste de tous les facteurs de n triés par ordre croissant, renvoyez le kième facteur dans cette liste ou renvoyez -1 si n a moins de k facteurs.

La solution évidente

Eh bien, si vous êtes comme moi, votre première pensée a été de parcourir chaque nombre de 1 à n, de vérifier si c'est un facteur, et s'il est dans l'indice k souhaité, de le renvoyer.

Le code ressemble à ceci :

def getkthFactorOfN(n, k):
    result = 0
    for i in range(1, n + 1):
        if n % i == 0:
            result = result + 1
            if result == k:
                return i
    return -1

Tout va bien, mais c'est "seulement" O(n). Après tout, il n'y a qu'une seule boucle et elle monte jusqu'au n 1.
Toute autre opération est ignorée lors de la prise en compte de la notation temporelle.

Mais, mon ami, il y a un piège.

Comprendre les facteurs

Si vous y réfléchissez, les facteurs se « reflètent » après un certain point.

Prenons, par exemple, le nombre 81. Ses facteurs sont [1, 3, 9, 27], où :

• 1*81 = 81
• 3*27 = 81
• 9*9 = 81
• 27*3 = 81
• 81 * 1 = 81

Si vous ne comptez pas le chiffre 9, les opérations sont simplement répétées et inversées. Si vous divisez n par l'un de ses facteurs, vous obtenez un autre facteur.
Attendez-vous à la racine carrée de n, où elle est elle-même au carré (duh).

Armés de ces connaissances, nous savons maintenant que nous n'avons pas besoin de parcourir la boucle jusqu'à n fois (avec range(1, n 1)), mais simplement jusqu'à math.sqrt(n). Après cela, nous avons tous les facteurs dont nous avons besoin !

La solution pas si évidente

Maintenant que nous avons tout ce dont nous avons besoin, nous devons transformer cette boucle de 1 -> n à 1 -> carré n.

Je vais juste lancer le code ici et nous passerons en revue les lignes une par une.

def getkthFactorOfN(n, k):
    i = 1
    factors_asc = []
    factors_desc = []
    while i * i <= n:
        if n % i == 0:
            factors_asc.append(i)
            if i != n // i:
                factors_desc.append(n // i)
        i += 1
    if k <= len(factors_asc):
        return factors_asc[k-1]
    k -= len(factors_asc)
    if k <= len(factors_desc):
        return factors_desc[-k]
    return -1

Oof, c'est bien plus complexe. Décomposons-le :

Tout d'abord, nous initialisons i = 1. Cette variable sera utilisée comme « nombre auquel nous nous trouvons actuellement » lors de la recherche de facteurs.

Deuxièmement, nous allons créer deux tableaux : facteurs_asc et facteurs_desc. La magie ici est que nous allons ajouter des facteurs à factor_asc - ils sont nommés ainsi car ils seront automatiquement classés par ordre croissant.
Chaque fois que nous ajoutons quelque chose à Factors_asc, nous divisons n par celui-ci et l'ajoutons à Factors_desc. Logique similaire ici ; ils seront commodément ajoutés par ordre décroissant.

Ensuite, nous commençons notre boucle. Ici, je l'ai changé pour être while i * i <= n, puisque nous nous arrêtons lorsque nous atteignons la racine de n.

On commence par vérifier si le nombre actuel est un facteur (n % i == 0). Si tel est le cas, nous pouvons l'ajouter à notre tableau factor_asc.

Ensuite, nous obtenons le "facteur inverse" de i. Nous pouvons le faire en vérifiant si i != n // i, ou en d'autres termes, si ce n'est pas la racine. En effet, la racine ne doit pas être dupliquée dans les deux tableaux. Si ce n'est pas le cas, nous obtenons le facteur inversé en exécutant n // i et en ajoutant le résultat dans factor_desc.

Après cela, nous ajoutons 1 à i et continuons notre boucle.

Une fois la boucle terminée, nous devons avoir toutes les factorielles dont nous avons besoin.

On commence par vérifier si k est dans la première moitié incluant la racine (qui peut être interprétée comme le milieu) avec if k <= len(factors_asc). Si tel est le cas, récupérez l'index de ce tableau (rappelez-vous : les tableaux commencent à zéro !).

Sinon, il faut soustraire la quantité de facteurs trouvés de k et vérifier à nouveau - avec k -= len(factors_asc) et si k <= len(factors_desc).

Si k est à l'intérieur de factor_desc, obtenez sa valeur avec factor_desk[-k] (du dernier au premier).

Si tout échoue, renvoie -1.

La courbe

Si vous vous demandez où il atterrit dans le graphique des courbes, ce serait entre O(n) et O(log n), étant meilleur que le premier et pire que ce dernier. Voici un graphique :

Disponible chez Mathspace

Conclusion

C'était une balade à découvrir et à faire des recherches. Merci beaucoup d'avoir lu jusqu'ici.

Si vous souhaitez être plus optimisé, vous pouvez créer des variables factor_asc_len et factor_desc_len et ajouter 1 à chaque fois que vous ajoutez une valeur à ces tableaux, afin que la méthode len() n'ait pas besoin d'être appelée, puisque cette méthode est O(n) donc cela peut avoir un impact sur la notation temporelle.

Bonne chance dans vos études et à la prochaine fois !

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!