Shannon Information Entropy as Complexity Metric of Source Code

M. Cholewa (Univ. of Silesia, Poland)

This paper describes method, which allows comparing complexity of two or more source codes written in any programming language. The method is suitable to get the knowledge which programming language more compactly describes a given algorithm. In experiments carried out popular quick sort algorithm was analyzed. This algorithm was written in 10 most popular program languages and then complexity of source codes can be compared. The complexity is calculated using the Shannon entropy formula with statistics of syntactic units (e.g. keywords, literals, operators, etc.). All complexities was compared and discovered the source code (and hence language that generated this code) with lower entropy as optimal. The optimal source code will have smaller number of keywords, declarations, etc. compared to not optimized code. In practice, proposed approach allows to use another syntactic units (e.g. use more operators and less identifiers) to build an optimal source code according to minimization entropy rule. Proposed method is universal and can be applied to analysis of any source codes of computer programs. It should be noted that proposed measure does not take into consideration semantics of a programming language.