How can we classify various Algorithms?

How can we classify various Algorithms?

I have heard various names: Divide & Conquer Algorithms, Deterministic Algorithms, Probabilistic Algorithms, In-place Algorithms and so on.

Do they form any kind of classification hierarc开发者_如何学Chy?

Please provide me with any web link.

There are some different classification for algorithms:

The way they solve the problems

classical algorithms:

• Divide & Conquer like binary search
• Greedy Algorithms like finding maximum in list, or maximum job allocation with unweighted job values.
• Dynamic Programming, like LCS
• Backtracking, like 8 queen, and all NPC algorithms.
• Sorting Algorithms, Sorting has specific methodology and used in wide range
• Linear Programming
• Graph Algorithms

Non classical ones:

• Random walk
• Genetic algorithm
• Markov Chain
• Approximation Algorithms
• Neural network, ...

But this algorithms are deterministic or non deterministic means for each run on the specific input they will get same result (deterministic) or different result(non deterministic).

Also this algorithms have too many different problem in their, and each of problems uses hybrid of all algorithms, for example TSP in euclidean graph can be approximated by using dfs and graph algorithms, and random walk, .... and ATSP (TSP in Asymmetric graphs) can be approximated by combination of Linear Programming and some advance graph algorithms.

But there is famous classification for problems and we can extend it to algorithms which is on time complexity (Also memory but this days memory is not concern as time):

• P
• NP
• NPC
• NPC strong
• NP Hard
• co-NP
• ...

There is no universal classification of algorithms. Broadly it can according to the design pattern followed, the problem that the algorithm solves or the complexity. You can create hierarchies by combining these classifications. For example, sorting algorithms can be subdivided into groups based on design patterns or by complexity.

Some more details are given here - http://www.scriptol.com/programming/algorithms-classification.php

You can have a look at the The Stony Brook Algorithm Repository. This is a classification of algorithms based on its purposes.

There are enormous numbers of algorithm classification schemes, some more useful than others (for an example of a very foolish scheme, consider classifying by the checksum of the algorithm description!) and this is a consequence of the classifications being not so much a fundamental property of the algorithms, but rather of what we know about them. Classifying knowledge is very difficult, and tends to produce many overlapping classifications; the whole field of building such classifications is called ontology. (Confusingly, the word “ontology” is also attached to computer-readable classification schemes in languages like OWL.)

As such, it's an open question whether there's a useful hierarchy of classifications, and doubly so if there is a useful hierarchy when it comes to algorithms. I suspect that the answer is “not really”, and urge you to just be flexible when it comes to classifying things.

You can classify algorithms as you wish, as serves your purposes best. The outline classification you propose, which classifies algorithms according to their outline design, looks OK. Another approach would be to classify them by purpose: Sorting, Searching, Multiplication, etc. Another approach might be to classify them by complexity: O(1), O(n), O(log n), O(n³) etc. Each individual algorithm you care to classify will fit into any of these classification schemes.

You could define a hierarchical classification scheme if that's what you want: sorting/random-inputs, sorting/nearly-sorted-inputs, sorting/nearly-unsorted-inputs.

But there's no single right or wrong classification scheme for algorithms, what you choose should depend on what you intend to do with it.

As for web-links, I'll leave them to others.