logo

Aprendre estructures de dades i algorismes | Tutorial DSA

Estructures i algorismes de dades (DSA) fan referència a l'estudi dels mètodes d'organització i emmagatzematge de dades i al disseny de procediments (algorismes) per a la resolució de problemes, que operen sobre aquestes estructures de dades. DSA és una de les habilitats més importants que ha de tenir tot estudiant d'informàtica. Sovint es veu que les persones amb bons coneixements d'aquestes tecnologies són millors programadors que altres i, per tant, aconsegueixen les entrevistes de gairebé tots els gegants tecnològics. Això Tutorial DSA pretén ajudar-vos a aprendre estructures i algorismes de dades (DSA) de manera ràpida i senzilla.



Taula de contingut

  • Aprendre algorismes
  • Coneix les complexitats
  • Fulles de trampes de problemes de pràctica
  • Formulari complet de DSA

    El terme DSA significa Estructures i algorismes de dades , en el context de la informàtica.

    Què és DSA?

    Estructures i algorismes de dades (DSA) fan referència a l'estudi dels mètodes d'organització i emmagatzematge de dades i al disseny de procediments (algorismes) per a la resolució de problemes, que operen sobre aquestes estructures de dades.



    Com aprendre DSA?

    El primer i més important és dividir el procediment total en petites peces que s'han de fer de manera seqüencial. El procés complet per aprendre DSA des de zero es pot dividir en 5 parts:

    1. Apreneu almenys un llenguatge de programació (deixem això a la vostra elecció.)
    2. Aprendre estructures de dades
    3. Aprendre algorismes
    4. Coneix les complexitats del temps i l'espai
    5. Problemes de pràctica sobre DSA
    Com aprendre DSA?

    Com aprendre DSA?

    Esperem que hàgiu après un llenguatge de programació de la vostra elecció, anem a avançar amb el següent pas per aprendre DSA en aquest tutorial DSA.



    Aquí ve l'etapa més important i més esperada del full de ruta per aprendre l'estructura de dades i l'algorisme: l'etapa en què comenceu a aprendre sobre DSA. El tema de DSA consta de dues parts:

    • Estructures de dades
    • Algorismes

    Tot i que són dues coses diferents, estan molt interrelacionades, i és molt important seguir el camí correcte per aprendre-les de la manera més eficient. Si esteu confós sobre quin aprendre primer, us recomanem que reviseu la nostra anàlisi detallada sobre el tema: Aquí hem seguit el flux d'aprenentatge d'una estructura de dades i després els algorismes més relacionats i importants utilitzats per aquesta estructura de dades.

    Aprendre estructures de dades

    Estructures de dades són components essencials que ajuden a organitzar i emmagatzemar dades de manera eficient a la memòria de l'ordinador. Proporcionen una manera de gestionar i manipular les dades de manera eficaç, permetent operacions d'accés, inserció i supressió més ràpides. Les estructures de dades comunes inclouen matrius, llistes enllaçades, piles, cues, arbres i gràfics , cadascun amb finalitats específiques en funció dels requisits del problema en qüestió. Entendre les estructures de dades és fonamental per dissenyar algorismes eficients i optimitzar el rendiment del programari.

    Matriu és una estructura de dades lineal que emmagatzema una col·lecció d'elements del mateix tipus de dades. Els elements s'assignen memòria contigua, permetent l'accés en temps constant. Cada element té un número d'índex únic.

    • Operacions a Array:
      • Travessia : Iterar a través dels elements d'una matriu.
      • Inserció : Afegeix un element a la matriu en un índex específic.
      • Supressió : eliminació d'un element de la matriu en un índex específic.
      • Buscant : trobar un element a la matriu pel seu valor o índex.
    • Tipus de matrius :
      • Matriu unidimensional : una matriu simple amb una sola dimensió.
      • Matriu multidimensional : una matriu amb múltiples dimensions, com ara una matriu.
    • Aplicacions de Array :
      • Emmagatzematge de dades de manera seqüencial
      • Implementació de cues, piles i altres estructures de dades
      • Representació de matrius i taules
    • Temes relacionats amb Array:
      • Tutorial de matrius
      • Els 50 principals problemes de codificació de matrius per a entrevistes
      • Practicar problemes amb Arrays

    2. Corda

    A corda és una seqüència de caràcters, que normalment s'utilitza per representar text. Es considera un tipus de dades que permet la manipulació i el processament de dades textuals en programes informàtics.

    • Operacions sobre String :
      • Concatenació : Unint dues cordes juntes.
      • Comparació : Comparació lexicogràfica de dues cadenes.
      • Subcadena extracció : Extracció d'una subcadena d'una cadena.
      • Cerca : cerca d'una subcadena dins d'una cadena.
      • Modificació : Canviar o substituir caràcters dins d'una cadena.
    • Aplicacions de String :
      • Tractament de textos
      • Coincidència de patró
      • Validació de dades
      • Gestió de bases de dades
    • Articles Relacionats:
      • Tutorial de cordes
      • Els 50 principals problemes de codificació de cadenes per a entrevistes
      • Pràctica de problemes sobre corda

    3. Llistes enllaçades

    A llista enllaçada és una estructura de dades lineal que emmagatzema dades en nodes, que estan connectats per punters. A diferència de les matrius, les llistes enllaçades no s'emmagatzemen en ubicacions de memòria contigües.

    • Característiques de la llista enllaçada:
      • Dinàmic : les llistes enllaçades es poden redimensionar fàcilment afegint o eliminant nodes.
      • No contigus : Els nodes s'emmagatzemen en ubicacions de memòria aleatòries i es connecten mitjançant punters.
      • Accés seqüencial : només es pot accedir als nodes de manera seqüencial, començant pel cap de llista.
    • Operacions a la llista enllaçada:
      • Creació : Crear una nova llista enllaçada o afegir un nou node a una llista existent.
      • Travessia : Iterar per la llista i accedir a cada node.
      • Inserció : Afegeix un nou node en una posició específica de la llista.
      • Supressió : eliminació d'un node de la llista.
      • Cerca : Trobar un node amb un valor específic a la llista.
    • Tipus de llista enllaçada :
      • Llista enllaçada individualment : Cada node apunta al següent node de la llista.
      • Llista doblement enllaçada : Cada node apunta tant al següent com al anterior de la llista.
      • Llista enllaçada circular : L'últim node apunta cap al primer node, formant un bucle circular.
    • Aplicacions de Llista Enllaçada :
      • Les llistes enllaçades s'utilitzen en diverses aplicacions, com ara:
      • Implementació de cues i piles
      • Representació de gràfics i arbres
      • Manteniment de dades ordenades
      • Gestió de la memòria
    • Temes relacionats:
      • Tutorial de llista enllaçada
      • Els 50 principals problemes de la llista enllaçada per a entrevistes
      • Practicar problemes sobre llistes enllaçades

    4. Matriu/quadrícula

    A matriu és una matriu bidimensional d'elements, disposats en files i columnes. Es representa com una quadrícula rectangular, amb cada element a la intersecció d'una fila i una columna.

    • Conceptes clau:
      • Files : Línies horitzontals d'elements en una matriu.
      • Columnes : Línies verticals d'elements en una matriu.
      • Dimensions : el nombre de files i columnes d'una matriu (p. ex., una matriu 3×4 té 3 files i 4 columnes).
      • Element Accés : Es pot accedir als elements mitjançant índexs de fila i columna (p. ex., M[2][3] fa referència a l'element de la fila 2, columna 3).
    • Aplicacions de Matrix/Grid :
      • Processament d'imatge
      • Anàlisi de dades
      • Problemes d'optimització
    • Articles Relacionats:
      • Tutorial de matriu/quadrícula
      • Els 50 principals problemes de Matrix/Grid per a entrevistes
      • Pràctica de problemes sobre matriu/quadrícula

    5. Pila

    Pila és una estructura de dades lineal que segueix un ordre particular en què es realitzen les operacions. L'ordre pot ser LIFO (últim en entrar, primer en sortir) o FILO (primer en entrar, últim sortit) . LIFO implica que l'element que s'insereix per últim, surt primer i FILA implica que l'element que s'insereix primer surt el darrer.

    • Operació a la pila :
      • Empènyer : Afegeix un element a la part superior de la pila
      • Pop : elimina i torna l'element a la part superior de la pila
      • Ullada : retorna l'element a la part superior de la pila sense eliminar-lo
      • Mida : Retorna el nombre d'elements de la pila
      • Està buit : Comprova si la pila està buida
    • Aplicacions de Stack :
      • Crides de funció
      • Avaluació de l'expressió
      • Fes marxa enrere
      • Desfer/refer operacions
    • Temes relacionats a Stack:
      • Tutorial de pila
      • Els 50 principals problemes a la pila per a entrevistes
      • Practica problemes a Stack

    6. Cua

    A Cua L'estructura de dades és un concepte fonamental en informàtica utilitzat per emmagatzemar i gestionar dades en un ordre específic. Segueix el principi de Primer a entrar, primer a sortir ( FIFO ), on el primer element afegit a la cua és el primer que s'elimina

    • Operació a la cua :
      • Cua : afegeix un element a la part posterior de la cua
      • D'acord amb : elimina un element de la part davantera de la cua
      • Ullada : recupera l'element frontal sense treure'l
      • Està buit : Comprova si la cua està buida
      • Està ple : Comprova si la cua està plena
    • Tipus de cua :
      • Cua circular : L'últim element es connecta amb el primer element
      • Cua de dos extrems (Deque) : Les operacions es poden realitzar des dels dos extrems
      • Cua de prioritats : Els elements s'organitzen en funció de la prioritat
    • Aplicacions de la Cua :
      • Programació de treballs
      • Cua de missatges
      • Modelatge de simulació
      • Memòria de dades
    • Temes relacionats:
      • Tutorial de cua
      • Els 50 principals problemes a la cua per a les entrevistes
      • Practica problemes a la cua

    7. Munt

    A Munt és una estructura de dades d'arbre binari completa que compleix la propietat heap: per a cada node, el valor dels seus fills és menor o igual al seu propi valor. Normalment s'utilitzen munts per implementar cues de prioritat , on l'element més petit (o més gran) està sempre a l'arrel de l'arbre.

    • Operacions de Heap :
      • Insereix : Afegeix un nou element al munt mantenint les propietats del munt.
      • Extracte-Màx./Extracte-Min : elimina l'element arrel i reestructura el munt.
      • Tecla Augment/Disminució : Actualitza el valor d'un node i reestructura la pila.
    • Tipus de pila :
      • Max-Heap : El node arrel té el valor màxim entre els seus fills.
      • Min-Heap : El node arrel té el valor mínim entre els seus fills.
    • Aplicacions de Heap :
      • Cues de prioritat
      • Classificació
      • Algorismes gràfics (per exemple, algorisme de Dijkstra)
    • Articles Relacionats:
      • Tutorial Heap
      • Els 50 principals problemes a Heap per a entrevistes
      • Problemes de pràctica en Heap

    8. Hash

    Hashing és una tècnica que genera una sortida de mida fixa (valor hash) a partir d'una entrada de mida variable mitjançant fórmules matemàtiques anomenades funcions hash . El hashing s'utilitza per determinar un índex o una ubicació per emmagatzemar un element en una estructura de dades, permetent una recuperació i inserció eficients.

    • Conceptes clau:
      • Funció hash : una funció matemàtica que assigna una entrada a un valor hash.
      • Taula hash : una estructura de dades que emmagatzema parells clau-valor, on la clau és un valor hash i el valor són les dades reals.
      • Col·lisió : Quan dues claus diferents produeixen el mateix valor hash.
    • Tipus de funcions hash :
      • Mètode de divisió : divideix l'entrada per una constant i utilitza la resta com a valor hash.
      • Plaça Mitjana Mètode: quadrat l'entrada i pren els dígits del mig com a valor hash.
      • Mètode de plegat : Divideix l'entrada en blocs de la mateixa mida i els suma per obtenir el valor hash.
      • Mètode de multiplicació : Multiplica l'entrada per una constant i pren la part fraccional com a valor hash.
    • Tècniques de resolució de col·lisions :
      • Encadenament separat (hashing obert) : Emmagatzema els elements en col·lisió en una llista enllaçada amb el valor hash corresponent.
      • Adreçament obert (hashing tancat) : utilitza diverses estratègies per trobar una ubicació alternativa per als elements que xoquen dins de la taula hash.
    • Aplicacions de Hashing :
      • Emmagatzematge i recuperació de dades de manera eficient en bases de dades i sistemes de fitxers.
      • Verificació de contrasenyes i signatures digitals.
      • Distribució de sol·licituds entre diversos servidors.
      • Generar hash segurs per a la integritat i l'autenticació de les dades.
    • Articles Relacionats:
      • Tutorial Hash
      • Pràctica de problemes sobre hashing

    9. Arbre

    A arbre és una estructura de dades jeràrquica no lineal que consta de nodes connectats per vores, amb un node superior anomenat arrel i nodes que tenen nodes fills. S'utilitza en informàtica per organitzar les dades de manera eficient.

    com convertir una cadena en java enter
    • Travessa de l'arbre : Els mètodes de recorregut d'arbres s'utilitzen per visitar i processar nodes en una estructura de dades d'arbre. Els tres mètodes de travessa comuns són:
      • En ordre : Visiteu el subarbre esquerre, el node actual i després el subarbre dret.
      • Comanda prèvia : Visiteu el node actual, el subarbre esquerre i després el subarbre dret.
      • Post-comanda : Visiteu el subarbre esquerre, el subarbre dret i després el node actual.
    • Classificacions dels arbres:
      • Classificacions de Arbres fan referència a agrupar arbres en funció de determinades característiques o criteris. Això pot implicar categoritzar els arbres en funció del seu factor d'equilibri, grau de nodes, propietats d'ordenació, etc. A continuació es mostren algunes classificacions importants de l'arbre.
    Classificació Descripció

    Tipus

    Descripció

    Per Grau

    Els arbres es poden classificar en funció del nombre màxim de fills que pot tenir cada node.

    Arbre binari

    Cada node té com a màxim dos fills.

    Arbre ternari

    Cada node té com a màxim tres fills.

    Arbre N-ari

    Cada node té com a màxim N fills.

    Per Encàrrec

    Els arbres es poden classificar segons l'ordre dels nodes i subarbres

    Arbre de cerca binari (BST)

    Fill esquerre

    Munt

    Arbre binari especialitzat amb la propietat heap.

    Per Balanç

    Els arbres es poden classificar en funció del seu equilibri.

    Arbre Equilibrat

    Les altures dels subarbres difereixen com a màxim en un. Alguns exemples inclouen arbres AVL i arbres vermell-negre.

    Arbre desequilibrat

    Les altures dels subarbres poden diferir significativament, afectant el rendiment en operacions com la cerca i la inserció.

    • Aplicacions dels arbres:
      • Sistemes de fitxers
      • Bases de dades
      • documents XML
      • Intel · ligència artificial
    • Articles Relacionats:
      • Tutorial Arbre
      • Els 50 principals problemes de codificació d'arbres
      • Practica problemes en Tree

    10. Gràfic

    A Gràfic és una estructura de dades no lineal que consisteix en un conjunt finit de vèrtexs (o nodes) i un conjunt d'arestes que connecten un parell de nodes.

    Aprendre algorismes

    Un cop aclarits els conceptes de Estructures de dades , ara és el moment de començar el teu viatge a través del Algorismes . Segons el tipus de naturalesa i ús, els algorismes s'agrupen en diverses categories, tal com es mostra a continuació:

    1. Algorisme de cerca

    Algorismes de cerca s'utilitzen per localitzar dades específiques dins d'un conjunt de dades més gran. Ajuda a trobar la presència d'un valor objectiu dins de les dades. Hi ha diversos tipus d'algorismes de cerca, cadascun amb el seu propi enfocament i eficiència.

    • Algoritmes de cerca més comuns:
      • Cerca lineal : Cerca iterativa d'un extrem a l'altre.
      • Cerca binària : cerca dividida i vençuda en una matriu ordenada, reduint a la meitat l'espai de cerca a cada iteració.
      • Cerca ternaria : Cerca dividida i conquerida en una matriu ordenada, dividint l'espai de cerca en tres parts a cada iteració.
    • Altres algorismes de cerca:
      • Salt de cerca
      • Cerca per interpolació
      • Cerca exponencial
    • Temes relacionats:
      • Pràctica de problemes sobre algorisme de cerca

    2. Algorisme d'ordenació

    Algorismes d'ordenació s'utilitzen per organitzar els elements d'una llista en un ordre específic, com ara numèric o alfabètic. Organitza els elements de manera sistemàtica, facilitant la cerca i l'accés a elements concrets.

    Hi ha molts tipus diferents d'algorismes d'ordenació. Alguns algorismes molt utilitzats són:

    Algorisme d'ordenació Descripció
    Classificació de bombolles Compara iterativament elements adjacents i els intercanvia si estan fora d'ordre. L'element més gran surt al final de la llista amb cada passada.
    Ordenació de la selecció Troba l'element mínim a la part no ordenada de la llista i l'intercanvia amb el primer element. Repeteix aquest procés fins que s'ordena tota la llista.
    Ordenació d'inserció Construeix la llista ordenada un element a la vegada inserint cada element no ordenat a la seva posició correcta a la part ordenada.
    Classificació ràpida Un algorisme de dividir i conquerir que selecciona un element pivot, divideix la llista en dues subllistes basades en el pivot i aplica recursivament el mateix procés a les subllistes.
    Fusionar Ordenar Un altre algorisme de divideix i conquereix que divideix recursivament la llista en subllistes més petites, les ordena i després les fusiona de nou per obtenir la llista ordenada.

    Temes relacionats:

    • Tutorial d'algorisme d'ordenació
    • Top Ordenació de preguntes i problemes de l'entrevista
    • Pràctica de problemes sobre algorisme d'ordenació

    3. Algoritme Divide and Conquer

    Divideix i conquereix Els algorismes segueixen una estratègia recursiva per resoldre problemes dividint-los en subproblemes més petits, resolent aquests subproblemes i combinant les solucions per obtenir la solució final.

    Passos:

    1. Divideix : Particioneu el problema en subproblemes més petits i independents.
    2. Conquerir : Resoldre recursivament cada subproblema.
    3. Combina : Combina les solucions dels subproblemes per obtenir la solució final.

    Exemples:

    • Merge Sort: divideix la matriu en dues meitats, ordena cada meitat de forma recursiva i fusiona les meitats ordenades.
    • Ordenació ràpida: selecciona un element de pivot, divideix la matriu en dos subarrays basats en el pivot i ordena de manera recursiva cada subbarray.
    • Cerca binària: divideix l'espai de cerca per la meitat repetidament fins que es troba l'element objectiu o s'esgota l'espai de cerca.

    Articles relacionats:

    variables globals js
    • Tutorial Divide and Conquer
    • Pràctica de problemes sobre l'algorisme Divide And Conquer

    4. Algorismes cobdiciosos

    Com el seu nom indica, aquest algorisme construeix la solució una peça a la vegada i tria la següent peça que ofereix el benefici més evident i immediat, és a dir, quina és l'opció més òptima en aquest moment. Per tant, els problemes en què triar l'òptima localment també condueix a les solucions globals són els més adequats per a Greedy.

    Alguns problemes importants dels algorismes cobdiciosos són:

    Algoritme Descripció
    Motxilla fraccionada Trobeu el valor total màxim dels articles que es poden col·locar a la motxilla, permetent la inclusió fraccionada dels articles.
    Algoritme de Dijkstra Troba el camí més curt des d'un vèrtex font fins a tots els altres vèrtexs d'un gràfic ponderat.
    Algoritme de Kruskal Troba l'arbre d'abast mínim d'un gràfic ponderat.
    Codificació Huffman Crea un codi de prefix òptim per a un conjunt de símbols, minimitzant la longitud total de la codificació.

    Articles relacionats:

    • Tutorial de Greedy Algorithm
    • Pràctica de problemes sobre l'algoritme Greedy

    5. Recursió

    Recursió és una tècnica de programació on una funció s'anomena dins de la seva pròpia definició. Normalment s'utilitza per resoldre problemes que es poden desglossar en casos més petits del mateix problema. Per exemple: Torres de Hanoi (TOH) , Càlcul factorial i Seqüència de Fibonacci etc.

    Passos :

    • Cas base : defineix una condició que atura les trucades recursives i proporciona una solució.
    • Cas recursiu : Definiu els passos per desglossar el problema en instàncies més petites i fer trucades recursives.
    • Tornar : Retorna la solució de les trucades recursives i combina-les per resoldre el problema original.

    El punt que fa de Recursion un dels algorismes més utilitzats és que constitueix la base de molts altres algorismes com ara Travessa d'arbres , Travessa de gràfics , Algorismes Divide and Conquers i Algoritmes de retrocés .

    Temes relacionats:

    • Tutorial de recursivitat
    • Funcions recursives
    • Recurs de cua
    • Els 50 principals problemes de l'algoritme de recursència per a l'entrevista
    • Pràctica de problemes sobre algorisme de recursència

    6. Algoritme de retrocés

    Com s'ha esmentat anteriorment, el Fes marxa enrere L'algorisme es deriva de l'algorisme de recursència, amb l'opció de revertir si una solució recursiva falla, és a dir, en cas que una solució falli, el programa es remunta al moment en què va fallar i es basa en una altra solució. Així, bàsicament, prova totes les solucions possibles i troba la correcta.

    Alguns problemes importants i més comuns dels algorismes de retrocés, que heu de resoldre abans de seguir endavant, són:

    Problema Descripció
    Problema de la gira del cavaller Trobar una seqüència de moviments d'un cavaller en un tauler d'escacs de manera que visiti cada casilla exactament una vegada.
    Rata en un laberint Trobar un camí des de la posició inicial fins a la sortida en un laberint, amb obstacles representats com a parets.
    Problema N-Queen Col·locar N dames en un tauler d'escacs N×N de manera que no hi hagi dues dames que s'ataquin entre elles.
    Problema de la suma del subconjunt Determinar si existeix un subconjunt del conjunt donat amb una suma determinada.
    Sudoku Resoldre un trencaclosques de quadrícula de 9×9 amb números de l'1 al 9 de manera que cada fila, columna i subquadrícula de 3×3 contingui tots els dígits sense repetició.

    Article relacionat:

    • Tutorial de retrocés
    • Practicar problemes sobre l'algorisme de retrocés

    7. Programació dinàmica

    Programació dinàmica és un mètode utilitzat en matemàtiques i informàtica per resoldre problemes complexos desglossant-los en subproblemes més simples. En resoldre cada subproblema només una vegada i emmagatzemar els resultats, evita càlculs redundants, donant lloc a solucions més eficients per a una àmplia gamma de problemes.

    Conceptes clau:

    • Subestructura òptima : La solució òptima a un problema es pot construir a partir de les solucions òptimes als seus subproblemes.
    • Subproblemes superposats : Els subproblemes es repeteixen sovint en el problema més gran, donant lloc a càlculs redundants.
    • Memoització / Tabulació : Emmagatzemar les solucions dels subproblemes per evitar el recàlcul.

    Alguns problemes importants i més comuns dels algorismes de programació dinàmica, que heu de resoldre abans de seguir endavant, són:

    Problema Descripció
    Seqüència de Fibonacci Generació de nombres de Fibonacci mitjançant programació dinàmica per evitar càlculs redundants.
    Subseqüència comuna més llarga Trobar la subseqüència més llarga comuna a dues seqüències.
    Subseqüència creixent més llarga Trobar la subseqüència més llarga d'una seqüència donada en què els elements estan ordenats en ordre creixent.
    0/1 problema de la motxilla Determinar el valor màxim que es pot obtenir seleccionant articles amb pesos i valors determinats, sense superar un límit de pes especificat.
    Problema de tall de varetes Maximitzar el benefici tallant una vareta de longitud determinada en trossos i venent-les segons els preus donats.
    Problema de canvi de moneda Determinar el nombre de maneres de fer canvis per a una quantitat determinada utilitzant un conjunt determinat de denominacions de monedes.
    Edita la distància Trobar el nombre mínim d'operacions (inserció, supressió, substitució) necessàries per convertir una cadena en una altra.
    Problema de la suma del subconjunt Determinar si existeix un subconjunt d'un conjunt donat amb una suma determinada.
    Subseqüència palindròmica més llarga Trobar la subseqüència més llarga d'una seqüència determinada que és un palíndrom.
    Suma màxima de Subbarray Trobar la subarray contigua amb la suma més gran dins d'una matriu unidimensional donada.
    Suma del subconjunt de la partició igual Determinar si és possible dividir un conjunt donat en dos subconjunts amb la mateixa suma.
    Ruta de cost mínim Trobar el camí del cost mínim des de l'extrem superior esquerre fins a l'extrem inferior dret d'una quadrícula determinada.
    Producte màxim Subbarray Trobar la subarray contigua amb el producte més gran dins d'una matriu unidimensional determinada.

    Articles relacionats:

    • Tabulació vs memorització
    • Com resoldre un problema de programació dinàmica?
    • Tutorial de programació dinàmica
    • Els 50 principals problemes de codificació de programació dinàmica per a entrevistes
    • Pràctica de problemes sobre algorisme de programació dinàmica

    8. Algorismes gràfics :

    Algorismes gràfics en estructures de dades i algorismes (DSA) són un conjunt de tècniques i mètodes utilitzats per resoldre problemes relacionats amb gràfics, que són una col·lecció de nodes i arestes. Aquests algorismes estan dissenyats per realitzar diverses operacions sobre gràfics, com ara buscar, recórrer, trobar el camí més curt , i determinant connectivitat . Són essencials per resoldre una àmplia gamma de problemes del món real, com ara l'encaminament de la xarxa, l'anàlisi de xarxes socials i l'assignació de recursos.

    Tema

    Descripció del tema

    Algoritme Descripció de l'algoritme
    Travessia gràfica

    Tècniques per visitar tots els vèrtexs d'un gràfic.

    Cerca en profunditat (DFS) Explora el més lluny possible al llarg de cada branca abans de fer marxa enrere.
    Cerca d'amplada primer (BFS) Explora els vèrtexs veïns abans de passar al següent nivell de vèrtexs.

    Arbres allargats mínims

    Els arbres d'abast mínim són els arbres més petits que connecten tots els nodes en un gràfic sense formar cicles, aconseguits afegint les arestes més curtes possibles.

    Algoritme de Kruskal

    Troba un arbre abastant mínim per a un gràfic ponderat connectat. Afegeix la vora de pes més petita que no forma un cicle.

    Algoritme de Prim

    També troba un arbre abastant mínim per a un gràfic ponderat connectat. Afegeix la vora de pes més petita que connecta dos arbres.

    Ordenació topològica

    L'ordenació topològica és una ordenació lineal dels vèrtexs en un graf acíclic dirigit (DAG) de manera que per a cada aresta dirigida des del vèrtex u fins al vèrtex v, u va abans de v en l'ordenació.

    Algoritme de Kahn L'algoritme de Kahn troba un ordenament topològic d'un graf acíclic dirigit (DAG).
    Algorisme basat en DFS L'algoritme basat en DFS utilitza Depth-First Search per realitzar l'ordenació topològica en un gràfic acíclic dirigit (DAG).

    El camí més curt

    Un camí més curt en un gràfic és el camí entre dos vèrtexs en un gràfic que té la suma mínima de pesos al llarg de les seves vores en comparació amb la resta de camins entre els mateixos dos vèrtexs.

    llenguatge genial

    Algoritme de Dijkstra

    Algorisme cobdiciós per trobar el camí més curt entre tots els nodes en temps O(E * V logV).

    Algoritme de Floyd-Warshall

    Troba el camí més curt entre tots els parells de nodes en temps O(V^3).

    Algoritme de Bellman Ford

    Troba el camí més curt des d'una única font en temps O(V * E).

    Algoritme de Johnson

    Troba els camins més curts entre tots els parells de vèrtexs en temps O(V^2 logV + V * E).

    Components fortament connectats

    Un component fortament connectat (SCC) d'un graf dirigit és un conjunt màxim de vèrtexs de manera que hi ha un camí des de cada vèrtex del conjunt fins a tots els altres vèrtexs del conjunt.

    Algoritme de Kosaraju

    L'algoritme de Kosaraju és un algorisme de dos passos que troba de manera eficient els components fortament connectats (SCC) d'un gràfic dirigit.

    Algoritme de Tarjan

    L'algoritme de Tarjan és un altre algorisme eficient per trobar SCC en un gràfic dirigit

    Temes relacionats:

    • Tutorial de gràfics
    • Els 50 principals problemes de codificació de gràfics per a entrevistes
    • Problema de pràctica sobre algorismes gràfics

    9 . Cerca de patrons

    Cerca de patrons és una tècnica fonamental en DSA utilitzada per trobar ocurrències d'un patró específic dins d'un text determinat.

    A continuació es mostren alguns algorismes estàndard de cerca de patrons:

    Algoritme Descripció Complexitat temporal
    Força bruta Compara el patró amb cada subcadena del text O(mn)
    Knuth-Morris-Pratt Utilitza una funció de fallada prèviament calculada per saltar comparacions innecessàries O(m + n)
    Boyer-Moore Compara el patró de dreta a esquerra, saltant caràcters en funció de l'últim desajust O(mn)
    Rabin-Karp Utilitza hashing per comprovar ràpidament si hi ha possibles coincidències O(m + n)

    Temes relacionats:

    • Tutorial de cerca de patrons
    • Problema de pràctica activat Cerca de patrons

    10 . Algorismes matemàtics

    Algorismes matemàtics són una classe d'algorismes que resolen problemes relacionats amb conceptes matemàtics. S'utilitzen àmpliament en diversos camps, inclosos els gràfics per ordinador, l'anàlisi numèrica, l'optimització i la criptografia.

    Algoritme Descripció
    GCD i LCM Troba el màxim comú divisor i el mínim comú múltiple de dos nombres.
    Factorització primeres Descompondre un nombre en els seus factors primers.
    Nombres de Fibonacci Genera la seqüència de Fibonacci, on cada nombre és la suma dels dos precedents.
    Nombres catalans Compteu el nombre d'expressions vàlides amb un nombre determinat de parells de parèntesis.
    Aritmètica modular Realitzar operacions aritmètiques sobre nombres mòdul d'un valor donat.
    Funció Totient d'Euler Compteu el nombre de nombres enters positius menors que un nombre donat que li són relativament primers.
    Càlculs nCr Calcula el coeficient binomial, que representa el nombre de maneres de triar r elements d'un conjunt de n elements.
    Nombres primers i proves de primalitat Determina si un nombre donat és primer i troba els nombres primers de manera eficient.
    Algorismes de tamís Troba tots els nombres primers fins a un límit determinat.

    Temes relacionats:

    • Problema de pràctica sobre algorisme matemàtic

    11. Algorismes geomètrics

    Algorismes geomètrics són una classe d'algorismes que resolen problemes relacionats amb la geometria. Els algorismes geomètrics són essencials per resoldre una àmplia gamma de problemes en informàtica, com ara:

    Algoritme Descripció
    Casc convex Troba el polígon convex més petit que conté un conjunt de punts.
    Parell de punts més proper Troba els dos punts d'un conjunt més propers l'un a l'altre.
    Intersecció de línies Determina si dues rectes es tallen i, si és així, troba el punt d'intersecció.
    Punt al polígon Determina si un punt donat es troba dins o fora d'un polígon.

    Temes relacionats:

    • Problema de pràctica sobre algorismes geomètrics

    12. Algorismes per bits

    Algorismes per bits són algorismes que operen sobre bits individuals de nombres. Aquests algorismes manipulen la representació binària dels nombres per realitzar tasques com ara manipulació de bits, operacions lògiques per bits (AND, OR, XOR), bits de canvi , i configuració o esborrant bits específics dins d'un nombre. Els algorismes bit a bit s'utilitzen habitualment tasques de programació, criptografia i optimització de baix nivell on es requereix una manipulació eficient de bits individuals.

    Tema Descripció
    Canvi de bits Desplaça els bits cap a l'esquerra o la dreta en un nombre especificat de posicions.
    Desplaçament a l'esquerra (<<) Desplaça els bits cap a l'esquerra, multiplicant efectivament el nombre per 2.
    Canvi a la dreta (>>) Desplaça els bits cap a la dreta, dividint efectivament el nombre per 2.
    Extracció de bits Ús de màscares per extreure bits específics d'un nombre enter.
    Bits de configuració Ús de màscares per establir bits específics a 1 en un nombre enter.
    Bits de neteja Ús de màscares per establir bits específics a 0 en un nombre enter.
    Bits de commutació Utilitzant XOR (^) per alternar bits específics en un nombre enter.
    Comptant Set bits Comptar el nombre de bits establerts (1s) en un nombre enter.

    Temes relacionats:

    • Tutorial d'algorismes per bits
    • Problema de pràctica sobre algorismes de bits

    13. Algorismes aleatoris

    Els algorismes aleatoris són algorismes que utilitzen l'aleatorietat per resoldre problemes. Fan servir inputs aleatoris per assolir els seus objectius, sovint conduint a solucions més senzilles o eficients.

    Tipus d'algorismes aleatoris:

    • Las Vegas : sempre produeix un resultat correcte, però el temps d'execució és aleatori.
    • Muntanya Carlo : pot produir un resultat incorrecte amb poca probabilitat, però el temps d'execució sol ser més ràpid.

    Algoritmes importants que utilitzen algorismes d'aleatorització:

    Algoritme Descripció
    QuickSort Un algorisme d'ordenació aleatòria amb una complexitat de temps mitjana de cas de O(n log n).
    Llista de salts Una estructura de dades aleatòria que proporciona operacions de cerca i inserció ràpides.
    Filtre de floració Una estructura de dades probabilística per a proves eficients de pertinença a conjunts.

    14. Algoritme de ramificació i lligat

    El Algoritme de ramificació i lligat és un mètode utilitzat en problemes d'optimització combinatòria per buscar sistemàticament la millor solució. Funciona dividint el problema en subproblemes més petits, o branques, i després eliminant determinades branques en funció dels límits de la solució òptima. Aquest procés continua fins que es troba la millor solució o s'han explorat totes les branques.

    Problemes estàndard sobre l'algoritme de ramificació i lligat:

    Problema únic Descripció
    Motxilla 0/1 amb Branch and Bound Detalls d'implementació de l'enfocament de branca i lligat per resoldre el problema de la motxilla 0/1.
    Motxilla 0/1 utilitzant Least Cost Branch and Bound Resolució del problema de la motxilla 0/1 utilitzant la tècnica de ramificació i lligat de menor cost.
    8 trencaclosques Problema amb Branch and Bound Aplicació de la branca i lligat a resoldre el problema de 8 trencaclosques, un popular joc de trencaclosques lliscant.
    N Queen Problema amb Branch and Bound Utilitzant la branca i obligat a trobar solucions al problema de N Queens, un problema clàssic d'escacs.

    Temes relacionats:

    • Tutorial d'algoritmes de branca i lligat

    Coneix les complexitats

    En Estructures i algoritmes de dades (DSA), l'objectiu principal és resoldre problemes de manera eficaç i eficient. Per determinar l'eficiència d'un programa, observem dos tipus de complexitats:

    1. Complexitat temporal : Això ens indica quant de temps triga a executar-se el nostre codi.
    2. Complexitat espacial : Això ens indica quanta memòria utilitza el nostre codi.

    Notació Asimptòtica :

    Per comparar l'eficiència dels algorismes, utilitzem la notació asimptòtica, una eina matemàtica que estima temps basat en mida d'entrada sense executar el codi. Se centra en el nombre d'operacions bàsiques del programa.

    Notació Descripció
    Big-O (Ο) Descriu el pitjor dels casos, proporcionant un límit de temps superior de l'algorisme.
    Omega (Ω) Descriu el millor dels casos, oferint un límit temporal inferior de l'algorisme.
    Theta (θ) Representa la complexitat mitjana d'un algorisme d'algorisme.

    La notació més utilitzada per a l'anàlisi de codi és Notació O gran , proporcionant un límit superior sobre el temps d'execució o l'ús de la memòria pel que fa a la mida d'entrada.

    Temes relacionats:

    Fulls de trucs de problemes de pràctica:

    Llistes de problemes seleccionades dels articles següents:

    • Full de ruta DSA de Sandeep Jain
    • FULL SDE: una guia completa per a la preparació de SDE
    • techcodeview.com Master Sheet - Llista de tots els Cheat Sheets