计算机算法和计算复杂性浅介

对计算复杂性的研究始于本世纪60年代末。当时离第一台电子计算机的发明已近20年。在这期间,计算机科学取得了巨大的成就,人们解决了为数众多靠人的笔难以完成的问题,但在某些问题面前却遇到了意想不到的困难。这些问题都是从理论上已证明可以用计算机解决的,解决这些问题的算法已编制出来。但是,所有这些的算法时间或存储空间的耗费都大得惊人。