Diferente pentru blog/numbers-everyone-should-know intre reviziile #29 si #28

Nu exista diferente intre titluri.

Diferente intre continut:

| 11 | n! | brute force, backtracking, next_permutation |   |
| 8 |  n^n^ | brute force, cartesian product |   |
These numbers aren't very precise, they assume in memory operations and some varying constant factors, but they do give a good starting point in your search for a solution that fits your problem and your data size.
 
Let's go through an example. Suppose you work for a GPS company and your project is to improve their directions feature. In school you've learned about using Dijkstra's algorithm to find the shortest path between two nodes in a graph. Knowing these numbers you will understand that it will take seconds to process a graph with millions of edges given that Dijkstra implementations have m log n time complexity (where m is the number of edges and n the number of nodes).
 
Now you face a few questions:
 
How fast do you want your code to be? seconds? hundreds of milliseconds?
 
Usually people feel something on the web is fast if it takes less then half a second to execute. So let's say half a second.
 
How big is your graph? Do you want to solve the problem for a city, a coutry or even a continent?
 
Each is about a magnitude larger than the other and may mean you need different approaches. Here are sizes for a few input sets:
|_. input |_. Europe |_. USA/CAN |_. USA (Tiger) |
| #nodes | 18 029 721 | 18 741 705 | 24 278 285 |
| #directed edges | 42 199 587 | 47 244 849 | 58 213 192 |
| #road categories | 13 | 13 | 4 |
 
From the given time limit it's obvious that pure Dijkstra won't do and we need to look at how other algorithms behave like A star search or http://algo2.iti.kit.edu/schultes/hwy/esa06HwyHierarchies.pdf
These numbers aren't very precise, they assume in memory operations and some varying constant factors, but they do give a good starting point in your search for a solution that fits your problem and your data size.

Nu exista diferente intre securitate.

Topicul de forum nu a fost schimbat.