Tabel cu complexitatile algoritmilor si operatiilor pe diverse structuri de date

data-structures
algorithms
complexity
o-notation

(Adavidoaiei Dumitru-Cornel) #1

As mai adauga Knuth Morrit Pratt folosit la cautarea unui substring intr-un string care are complexitate de O(n+k) bazat pe un tabel cu frecventa aparitiei caracterelor in string-uri spre deosebire metoda naiva de comparare caracter cu caracter care are O(n^2).

Un loc important il are si capitolul de grafuri si determinarea de drumuri in grafuri.

Sunt bine de stiut aceste lucruri, acesti algoritmi si structuri de date uneori se asambleaza ca un puzzle folosindu-se imaginatia pentru a obtine solutii optime la diverse probleme.


Cum se calculeaza eficienta unui algoritm(O)
(Adavidoaiei Dumitru-Cornel) #2

O carte buna care explica pe intelesul oricui a fost publicata de Teora pe vremuri in romana:


(Adavidoaiei Dumitru-Cornel) #3

http://upm.ro/intranet/ecalin/cd_educational/cd/progr/complexitate_curs.html


(cosmos) #4

MI-am amintit de acest articol. Prezinta intr-o maniera usor de inteles conceptele de analiza algoritmilor. Merita citit !

https://discrete.gr/complexity/


(Adavidoaiei Dumitru-Cornel) #5

Am zis sa postez si in limba romana poate atrag mai multa lume, desigur cea mai buna documentatie e in engleza noi doar o traducem.


(cosmos) #6

Documentatia buna se gaseste in toate limbile. Este important cum este scrisa. Poti sa gasesti si o documentatie prost scrisa si in engleza


(Adavidoaiei Dumitru-Cornel) #7

Engleza e limba internationala si cel mai mult research s-a facut in state.


(Adavidoaiei Dumitru-Cornel) #8

Ceva algoritmi si structuri de date, complexitate, subiecte clasice in computer science:

Mi se pare foarte interesant ca se fac data storage in node.js, cu noua paradigma async, await in javascript se apropie de C#.

Data storage de care va ziceam:

OrbitDB is a serverless, distributed, peer-to-peer database. OrbitDB uses IPFS as its data storage and IPFS Pubsub to automatically sync databases with peers. It’s an eventually consistent database that uses CRDTs for conflict-free database merges making OrbitDB an excellent choice for decentralized apps (dApps), blockchain applications and offline-first web applications.


(Adavidoaiei Dumitru-Cornel) #9

Un mic articol cu cele mai populare structuri de date, si complexitatea operatiilor pe acestea insert, remove, search, complexitate de timp si memorie.

Linked List
Stack
Queue
Binary Search Tree
Binary Heap
Trie
Sets
Maps
Hashtable
Graphs

Sunt structuri de date care se invata la cursurile de computer science in liceu sau facultate.

Si o carte cu metode si tehnici de programare dintre care
-1. Preface (8 pages)
0. Introduction (20 pages)

  1. Recursion (48 pages)
  2. Backtracking (26 pages)
  3. Dynamic Programming (62 pages)
  4. Greedy Algorithms (28 pages)
  5. Basic Graph Algorithms (38 pages)
  6. Depth-First Search (32 pages)
  7. Minimum Spanning Trees (16 pages)
  8. Shortest Paths (35 pages)
  9. All-Pairs Shortest Paths (18 pages)
  10. Maximum Flows & Minimum Cuts (26 pages)
  11. Applications of Flows and Cuts (26 pages)
  12. NP-Hardness (50 pages)
    http://jeffe.cs.illinois.edu/teaching/algorithms/?