Calculation of the Minimum Time Complexity Based on Information Entropy

Xue WU

Advances in Computer Science and Information Technology. Computer Science and Engineering. Second International Conference, CCSIT 2012, Bangalore, India, January 2-4, 2012. Proceedings, Part II

Research Article

Calculation of the Minimum Time Complexity Based on Information Entropy

Download

190 downloads

Cite: BibTeX Plain Text

@INPROCEEDINGS{10.1007/978-3-642-27308-7_41,
    author={Xue WU},
    title={Calculation of the Minimum Time Complexity Based on Information Entropy},
    proceedings={Advances in Computer Science and Information Technology. Computer Science and Engineering. Second International Conference, CCSIT 2012, Bangalore, India, January 2-4, 2012. Proceedings, Part II},
    proceedings_a={CCSIT PATR II},
    year={2012},
    month={11},
    keywords={information entropy time complexity algorithm entropy change},
    doi={10.1007/978-3-642-27308-7_41}
}

Xue WU
Year: 2012
Calculation of the Minimum Time Complexity Based on Information Entropy
CCSIT PATR II
Springer
DOI: 10.1007/978-3-642-27308-7_41

Xue WU¹^,*

1: Tsinghua University

*Contact email: wuxiqh@yahoo.cn

Abstract

In order to find out the limiting speed of solving a specific problem using computer, this essay provides a method based on the entropy of information. The relationship between the minimum time complexity and the information entropy change is illustrated. Several examples are served as evidence of such connection. Meanwhile some notices of modeling these problems are proposed. Finally, the nature of solving problems with computer programs is disclosed to support the theory and a redefinition of the information entropy in this field is proposed. This will develop a new field of science.

Keywords: information entropy time complexity algorithm entropy change

Published: 2012-11-09

: http://dx.doi.org/10.1007/978-3-642-27308-7_41