Learning Fundamentals: Data Structures and Algorithm Analysis in Perlby spectre9 (Beadle)
|on Apr 28, 2009 at 15:09 UTC||Need Help??|
I've seen a few questions recently on SOPW that mention algorithmic complexity (as Big O(*) notation) (see Wikipedia Big O Notation, Big-O Notation - What is it good for? and An informal introduction to O(N) notation.
While these original question and replies seem to have some basic knowledge, I personally find wisdom somewhat missing or am merely confused by the O(*) notation and analysis of cases.
Sources of Wisdom
Mark Allen Weiss (http://users.cs.fiu.edu/~weiss/) has authored a series of books entitled Data Structures and Algorithm Analysis. There are versions for Ada, Pascal, Java and C++. Many universities use these books as college textbooks, and I myself have saved Data Structures and Algorithm Analysis in PASCAL and use it to this day even though I only code in Perl.
As one would expect, Wikipedia has an article entitled Computational Complexity Theory that is a more general discussion of this subject than the specific case of O(*)
Basics of Expressing Complexity Measurements
Complexity cannot be expressed as merely an 'algorithms' complexity. One must be clear if one is talking about:
Therefore, O(*) being tossed out as a bare concept is vaneer glued particle board... it looks beautiful, but is unsuitable for a sturdy boat or a roof. O(*) must not be a veneer of "complexity" tossed over dull and simple questions. It is a formalization of specific 'worst-case' conditions of growth.
Initial conditions and bounds are quite important when discussing complexity. Some algorithms behave differently when tuned differently, or when conditions change. For some discussion (also mentioning Weiss's work) you may refer to Wikipedia's article on Shell Sort which also includes an example of Wikipedia's Algorithm Infobox which could provide a model for including 'facts' when discussing O(*) issues here on PM.
Criticism of "Wise Sounding" RTFM questions
While in no way elitist toward fellow Monks, I personally wish to see the Quality/Node ratio here on PM continue to rise. Therefore, I have to rap a few shoulders with a cane to wake from slumber real wisdom. We must always remain vigilent lest "number of writeups" become the Kismet of XP, rather than XP reflecting the wise output of Monks who employ Zazen (meditation).
Questions to PonderTherefore, I put these questions to my Fellow Monks.
Call to Action
Perhaps we need a more coherent effort to address Complexity Analysis to coagulate our vast knowledge toward a more elightening end.
Offer your Answers, fellow monks. However, should no node be found that can bring Satori, what monks would be willing to join me in Sesshin on this subject?
"Upgrade your gray matter, cause one day it may matter" -- DELTRON 3030