Introduction à la notation DSA et Big O
Notes pour maîtriser le DSA :
Le Master DSA sera « éligible » aux salaires élevés offerts aux S/w Ers.
DSA est la majeure partie du génie logiciel.
Avant d'écrire du code, assurez-vous de bien comprendre la situation dans son ensemble, puis approfondissez les détails.
Il s'agit de comprendre les concepts visuellement, puis de traduire ces concepts en code via n'importe quel l/g, car DSA est indépendant du langage.
Chaque concept à venir est en quelque sorte lié aux concepts précédents. Par conséquent, ne sautez pas de sujet et n'avancez pas à moins de maîtriser parfaitement le concept en le pratiquant.
Lorsque nous apprenons des concepts visuellement, nous obtenons une compréhension plus profonde du matériel, ce qui nous aide à conserver les connaissances plus longtemps.
Si vous suivez ces conseils, vous n'aurez rien à perdre.
Linear DS: Arrays LinkedList(LL) & Doubly LL (DLL) Stack Queue & Circular Queue Non-linear DS: Trees Graphs
Notation grand O
Il est essentiel de comprendre cette notation pour comparer les performances des algos.
C'est une manière mathématique de comparer l'efficacité des algorithmes.
Complexité temporelle
Plus le code s'exécute rapidement, plus il sera bas
V. impt pour la plupart des entretiens.
Complexité spatiale
Rarement considéré par rapport à la complexité temporelle en raison du faible coût de stockage.
Doit être compris, car un intervieweur peut également vous le demander.
Trois lettres grecques :
- Oméga
- Thêta
- Omicron c'est-à-dire Big-O [vu le plus souvent]
Cas pour algo
- Meilleur cas [représenté par Omega]
- Cas moyen [représenté par Theta]
- Pire des cas [représenté en utilisant Omicron]
Techniquement, il n'y a pas de meilleur cas de cas moyen Big-O. Ils sont désignés respectivement par oméga et thêta.
Nous mesurons toujours le pire des cas.
## O(n): Efficient Code Proportional Its simplified by dropping the constant values. An operation happens 'n' times, where n is passed as an argument as shown below. Always going to be a straight line having slope 1, as no of operations is proportional to n. X axis - value of n. Y axis - no of operations // O(n) function printItems(n){ for(let i=1; i<=n; i++){ console.log(i); } } printItems(9); // O(n) + O(n) i.e O(2n) operations. As we drop constants, it eventually becomes O(n) function printItems(n){ for(let i=0; i<n; i++){ console.log(i); } for(let j=0; j<n; j++){ console.log(j); } } printItems(10);
## O(n^2): Nested loops. No of items which are output in this case are n*n for a 'n' input. function printItems(n){ for(let i=0; i<n; i++){ console.log('\n'); for(let j=0; j<n; j++){ console.log(i, j); } } } printItems(4);
## O(n^3): No of items which are output in this case are n*n*n for a 'n' input. // O(n*n*n) function printItems(n){ for(let i=0; i<n; i++){ console.log(`Outer Iteration ${i}`); for(let j=0; j<n; j++){ console.log(` Mid Iteration ${j}`); for(let k=0; k<n; k++){ //console.log("Inner"); console.log(` Inner Iteration ${i} ${j} ${k}`); } } } } printItems(3); ## Comparison of Time Complexity: O(n) > O(n*n) ## Drop non-dominants: function xxx(){ // O(n*n) Nested for loop // O(n) Single for loop } Complexity for the below code will O(n*n) + O(n) By dropping non-dominants, it will become O(n*n) As O(n) will be negligible as the n value grows. O(n*n) is dominant term, O(n) is non-dominnat term here.
## O(1): Referred as Constant time i.e No of operations do not change as 'n' changes. Single operation irrespective of no of operands. MOST EFFICIENT. Nothing is more efficient than this. Its a flat line overlapping x-axis on graph. // O(1) function printItems(n){ return n+n+n+n; } printItems(3); ## Comparison of Time Complexity: O(1) > O(n) > O(n*n)
## O(log n) Divide and conquer technique. Partitioning into halves until goal is achieved. log(base2) of 8 = 3 i.e we are basically saying 2 to what power is 8. That power denotes the no of operations to get to the result. Also, to put it in another way we can say how many times we need to divide 8 into halves(this makes base 2 for logarithmic operation) to get to the single resulting target item which is 3. Ex. Amazing application is say for a 1,000,000,000 array size, how many times we need to cut to get to the target item. log(base 2) 1,000,000,000 = 31 times i.e 2^31 will make us reach the target item. Hence, if we do the search in linear fashion then we need to scan for billion items in the array. But if we use divide & conquer approach, we can find it in just 31 steps. This is the immense power of O(log n) ## Comparison of Time Complexity: O(1) > O(log n) > O(n) > O(n*n) Best is O(1) or O(log n) Acceptable is O(n)
O(n log n) : Used in some sorting Algos. Most efficient sorting algo we can make unless we are sorting only nums.
Tricky Interview Ques: Different Terms for Inputs. function printItems(a,b){ // O(a) for(let i=0; i<a; i++){ console.log(i); } // O(b) for(let j=0; j<b; j++){ console.log(j); } } printItems(3,5); O(a) + O(b) we can't have both variables equal to 'n'. Suppose a is 1 and b is 1bn. Then both will be very different. Hence, it will eventually be O(a + b) is what can call it. Similarly if these were nested for loops, then it will become O(a * b)
## Arrays No reindexing is required in arrays for push-pop operations. Hence both are O(1). Adding-Removing from end in array is O(1) Reindexing is required in arrays for shift-unshift operations. Hence, both are O(n) operations, where n is no of items in the array. Adding-Removing from front in array is O(n) Inserting anywhere in array except start and end positions: myArr.splice(indexForOperation, itemsToBeRemoved, ContentTobeInsterted) Remaining array after the items has to be reindexed. Hence, it will be O(n) and not O(0.5 n) as Big-O always meassures worst case, and not avg case. 0.5 is constant, hence its droppped. Same is applicable for removing an item from an array also as the items after it has to be reindexed. Finding an item in an array: if its by value: O(n) if its by index: O(1) Select a DS based on the use-case. For index based, array will be a great choice. If a lot of insertion-deletion is perform in the begin, then use some other DS as reindexing will make it slow.
Comparaison de la complexité temporelle pour n=100 :
O(1) = 1
O(log 100) = 7
O(100) = 100
O(n^2) = 10 000
Comparaison de la complexité temporelle pour n=1000 :
O(1) = 1
O(log 1000) = ~10
O(1000) = 1000
O(1000*1000) = 1 000 000
Nous nous concentrerons principalement sur ces 4 :
Big O(n*n) : boucles imbriquées
Big O(n) : Proportionnel
Big O (log n) : Diviser pour mieux régner
Grand O(1) : Constante
O(n!) se produit généralement lorsque nous écrivons délibérément du mauvais code.
O(n*n) est horrible Algo
O(n log n) est acceptable et utilisé par certains algos de tri
O(n) : Acceptable
O(log n), O(1) : Meilleur
La complexité spatiale est presque la même pour tous les DS, c'est-à-dire O(n).
La complexité spatiale variera de O(n) à O(log n) ou O(1) avec des algorithmes de tri
La complexité temporelle est ce qui varie en fonction de l'algorithme
La meilleure complexité temporelle pour le tri autre que les nombres comme la chaîne est O(n log n) qui est dans les tris rapides, par fusion, par temps et par tas.
La meilleure façon d’appliquer votre apprentissage est de coder autant que possible.
Sélectionner quel DS choisir dans quel énoncé de problème en fonction des avantages et des inconvénients de chaque DS.
Pour plus d'informations, référez-vous à : bigoheatsheet.com
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!

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

Video Face Swap
Échangez les visages dans n'importe quelle vidéo sans effort grâce à notre outil d'échange de visage AI entièrement gratuit !

Article chaud

Outils chauds

Bloc-notes++7.3.1
Éditeur de code facile à utiliser et gratuit

SublimeText3 version chinoise
Version chinoise, très simple à utiliser

Envoyer Studio 13.0.1
Puissant environnement de développement intégré PHP

Dreamweaver CS6
Outils de développement Web visuel

SublimeText3 version Mac
Logiciel d'édition de code au niveau de Dieu (SublimeText3)

Sujets chauds











Python convient plus aux débutants, avec une courbe d'apprentissage en douceur et une syntaxe concise; JavaScript convient au développement frontal, avec une courbe d'apprentissage abrupte et une syntaxe flexible. 1. La syntaxe Python est intuitive et adaptée à la science des données et au développement back-end. 2. JavaScript est flexible et largement utilisé dans la programmation frontale et côté serveur.

Le passage de C / C à JavaScript nécessite de s'adapter à la frappe dynamique, à la collecte des ordures et à la programmation asynchrone. 1) C / C est un langage dactylographié statiquement qui nécessite une gestion manuelle de la mémoire, tandis que JavaScript est dynamiquement typé et que la collecte des déchets est automatiquement traitée. 2) C / C doit être compilé en code machine, tandis que JavaScript est une langue interprétée. 3) JavaScript introduit des concepts tels que les fermetures, les chaînes de prototypes et la promesse, ce qui améliore la flexibilité et les capacités de programmation asynchrones.

Les principales utilisations de JavaScript dans le développement Web incluent l'interaction client, la vérification du formulaire et la communication asynchrone. 1) Mise à jour du contenu dynamique et interaction utilisateur via les opérations DOM; 2) La vérification du client est effectuée avant que l'utilisateur ne soumette les données pour améliorer l'expérience utilisateur; 3) La communication de rafraîchissement avec le serveur est réalisée via la technologie AJAX.

L'application de JavaScript dans le monde réel comprend un développement frontal et back-end. 1) Afficher les applications frontales en créant une application de liste TODO, impliquant les opérations DOM et le traitement des événements. 2) Construisez RestulAPI via Node.js et Express pour démontrer les applications back-end.

Comprendre le fonctionnement du moteur JavaScript en interne est important pour les développeurs car il aide à écrire du code plus efficace et à comprendre les goulots d'étranglement des performances et les stratégies d'optimisation. 1) Le flux de travail du moteur comprend trois étapes: analyse, compilation et exécution; 2) Pendant le processus d'exécution, le moteur effectuera une optimisation dynamique, comme le cache en ligne et les classes cachées; 3) Les meilleures pratiques comprennent l'évitement des variables globales, l'optimisation des boucles, l'utilisation de const et de locations et d'éviter une utilisation excessive des fermetures.

Python et JavaScript ont leurs propres avantages et inconvénients en termes de communauté, de bibliothèques et de ressources. 1) La communauté Python est amicale et adaptée aux débutants, mais les ressources de développement frontal ne sont pas aussi riches que JavaScript. 2) Python est puissant dans les bibliothèques de science des données et d'apprentissage automatique, tandis que JavaScript est meilleur dans les bibliothèques et les cadres de développement frontaux. 3) Les deux ont des ressources d'apprentissage riches, mais Python convient pour commencer par des documents officiels, tandis que JavaScript est meilleur avec MDNWEBDOCS. Le choix doit être basé sur les besoins du projet et les intérêts personnels.

Les choix de Python et JavaScript dans les environnements de développement sont importants. 1) L'environnement de développement de Python comprend Pycharm, Jupyternotebook et Anaconda, qui conviennent à la science des données et au prototypage rapide. 2) L'environnement de développement de JavaScript comprend Node.js, VScode et WebPack, qui conviennent au développement frontal et back-end. Le choix des bons outils en fonction des besoins du projet peut améliorer l'efficacité du développement et le taux de réussite du projet.

C et C jouent un rôle essentiel dans le moteur JavaScript, principalement utilisé pour implémenter des interprètes et des compilateurs JIT. 1) C est utilisé pour analyser le code source JavaScript et générer une arborescence de syntaxe abstraite. 2) C est responsable de la génération et de l'exécution de bytecode. 3) C met en œuvre le compilateur JIT, optimise et compile le code de point chaud à l'exécution et améliore considérablement l'efficacité d'exécution de JavaScript.
