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 <p>Oof, c'est bien plus complexe. Décomposons-le :</p> <p>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.</p> <p>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.<br> 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.</p><p>Ensuite, nous commençons notre boucle. Ici, je l'ai changé pour être while i * i </p><p>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.</p> <p>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.</p> <p>Après cela, nous ajoutons 1 à i et continuons notre boucle.</p> <p>Une fois la boucle terminée, nous devons avoir toutes les factorielles dont nous avons besoin.</p> <p>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 </p><p>Sinon, il faut soustraire la quantité de facteurs trouvés de k et vérifier à nouveau - avec k -= len(factors_asc) et si k </p><p>Si k est à l'intérieur de factor_desc, obtenez sa valeur avec factor_desk[-k] (du dernier au premier).</p> <p>Si tout échoue, renvoie -1.</p> <h2> La courbe </h2> <p>Si vous vous demandez où il atterrit dans le graphique des courbes, ce serait entre <strong>O(n)</strong> et <strong>O(log n)</strong>, étant meilleur que le premier et pire que ce dernier. Voici un graphique :</p> <p><img src="/static/imghwm/default1.png" data-src="https://img.php.cn/upload/article/000/000/000/173598658415895.jpg?x-oss-process=image/resize,p_40" class="lazy" alt="The Kth factor of N - an O(sqrt n) algorithm"><br> <em>Disponible chez Mathspace</em></p> <h2> Conclusion </h2> <p>C'était une balade à découvrir et à faire des recherches. Merci beaucoup d'avoir lu jusqu'ici.</p> <p>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 <strong>O(n)</strong> donc cela peut avoir un impact sur la notation temporelle.</p> <p>Bonne chance dans vos études et à la prochaine fois !</p>
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!

Ce tutoriel montre comment utiliser Python pour traiter le concept statistique de la loi de Zipf et démontre l'efficacité de la lecture et du tri de Python de gros fichiers texte lors du traitement de la loi. Vous vous demandez peut-être ce que signifie le terme distribution ZIPF. Pour comprendre ce terme, nous devons d'abord définir la loi de Zipf. Ne vous inquiétez pas, je vais essayer de simplifier les instructions. La loi de Zipf La loi de Zipf signifie simplement: dans un grand corpus en langage naturel, les mots les plus fréquents apparaissent environ deux fois plus fréquemment que les deuxième mots fréquents, trois fois comme les troisième mots fréquents, quatre fois comme quatrième mots fréquents, etc. Regardons un exemple. Si vous regardez le corpus brun en anglais américain, vous remarquerez que le mot le plus fréquent est "th

Python fournit une variété de façons de télécharger des fichiers à partir d'Internet, qui peuvent être téléchargés sur HTTP à l'aide du package ULLIB ou de la bibliothèque de demandes. Ce tutoriel expliquera comment utiliser ces bibliothèques pour télécharger des fichiers à partir des URL de Python. Bibliothèque de demandes Les demandes sont l'une des bibliothèques les plus populaires de Python. Il permet d'envoyer des demandes HTTP / 1.1 sans ajouter manuellement les chaînes de requête aux URL ou le codage de formulaire de post-données. La bibliothèque des demandes peut remplir de nombreuses fonctions, notamment: Ajouter des données de formulaire Ajouter un fichier en plusieurs parties Accéder aux données de réponse Python Faire une demande tête

Cet article explique comment utiliser la belle soupe, une bibliothèque Python, pour analyser HTML. Il détaille des méthodes courantes comme find (), find_all (), select () et get_text () pour l'extraction des données, la gestion de diverses structures et erreurs HTML et alternatives (Sel

Traiter avec des images bruyantes est un problème courant, en particulier avec des photos de téléphones portables ou de caméras basse résolution. Ce tutoriel explore les techniques de filtrage d'images dans Python à l'aide d'OpenCV pour résoudre ce problème. Filtrage d'image: un outil puissant Filtre d'image

Les fichiers PDF sont populaires pour leur compatibilité multiplateforme, avec du contenu et de la mise en page cohérents sur les systèmes d'exploitation, les appareils de lecture et les logiciels. Cependant, contrairement aux fichiers de texte brut de traitement Python, les fichiers PDF sont des fichiers binaires avec des structures plus complexes et contiennent des éléments tels que des polices, des couleurs et des images. Heureusement, il n'est pas difficile de traiter les fichiers PDF avec les modules externes de Python. Cet article utilisera le module PYPDF2 pour montrer comment ouvrir un fichier PDF, imprimer une page et extraire du texte. Pour la création et l'édition des fichiers PDF, veuillez vous référer à un autre tutoriel de moi. Préparation Le noyau réside dans l'utilisation du module externe PYPDF2. Tout d'abord, l'installez en utilisant PIP: pip is p

Ce tutoriel montre comment tirer parti de la mise en cache Redis pour augmenter les performances des applications Python, en particulier dans un cadre Django. Nous couvrirons l'installation redis, la configuration de Django et les comparaisons de performances pour mettre en évidence le bien

Le traitement du langage naturel (PNL) est le traitement automatique ou semi-automatique du langage humain. La PNL est étroitement liée à la linguistique et a des liens vers la recherche en sciences cognitives, psychologie, physiologie et mathématiques. En informatique

Cet article compare TensorFlow et Pytorch pour l'apprentissage en profondeur. Il détaille les étapes impliquées: préparation des données, construction de modèles, formation, évaluation et déploiement. Différences clés entre les cadres, en particulier en ce qui concerne le raisin informatique


Outils d'IA chauds

Undresser.AI Undress
Application basée sur l'IA pour créer des photos de nu réalistes

AI Clothes Remover
Outil d'IA en ligne pour supprimer les vêtements des photos.

Undress AI Tool
Images de déshabillage gratuites

Clothoff.io
Dissolvant de vêtements AI

AI Hentai Generator
Générez AI Hentai gratuitement.

Article chaud

Outils chauds

DVWA
Damn Vulnerable Web App (DVWA) est une application Web PHP/MySQL très vulnérable. Ses principaux objectifs sont d'aider les professionnels de la sécurité à tester leurs compétences et leurs outils dans un environnement juridique, d'aider les développeurs Web à mieux comprendre le processus de sécurisation des applications Web et d'aider les enseignants/étudiants à enseigner/apprendre dans un environnement de classe. Application Web sécurité. L'objectif de DVWA est de mettre en pratique certaines des vulnérabilités Web les plus courantes via une interface simple et directe, avec différents degrés de difficulté. Veuillez noter que ce logiciel

Télécharger la version Mac de l'éditeur Atom
L'éditeur open source le plus populaire

Dreamweaver Mac
Outils de développement Web visuel

PhpStorm version Mac
Le dernier (2018.2.1) outil de développement intégré PHP professionnel

Listes Sec
SecLists est le compagnon ultime du testeur de sécurité. Il s'agit d'une collection de différents types de listes fréquemment utilisées lors des évaluations de sécurité, le tout en un seul endroit. SecLists contribue à rendre les tests de sécurité plus efficaces et productifs en fournissant facilement toutes les listes dont un testeur de sécurité pourrait avoir besoin. Les types de listes incluent les noms d'utilisateur, les mots de passe, les URL, les charges utiles floues, les modèles de données sensibles, les shells Web, etc. Le testeur peut simplement extraire ce référentiel sur une nouvelle machine de test et il aura accès à tous les types de listes dont il a besoin.
