CODEWITHSUNDEEP
algorithm
user366312
user366312

Reputation: 16928

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 hierarchy?

Please provide me with any web link.

Upvotes: 3

Views: 3191

Answers (5)

Saeed Amiri
Saeed Amiri

Reputation: 22555

There are some different classification for algorithms:

The way they solve the problems

classical algorithms:

Non classical ones:

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
  • ...

Upvotes: 8

Donal Fellows
Donal Fellows

Reputation: 137597

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.

Upvotes: 1

High Performance Mark
High Performance Mark

Reputation: 78324

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(n3) 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.

Upvotes: 1

Luca Martini
Luca Martini

Reputation: 1474

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

Upvotes: 2

Pulkit Sinha
Pulkit Sinha

Reputation: 2784

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

Upvotes: 3

Related Questions