算法好坏的衡量尺度

独立于具体计算机的客观衡量标准
——问题的规模，基本运算，算法的计算量函数

问题的规模（大小，size）

一个或多个整数，作为输入数据的测量。
如：

1. 数表的长度（数据项个数）
2. 矩阵的最大维数（阶数）
3. 图中的顶点数和边数（图论中问题）

基本运算

解决给定问题时占支配地位的运算（一般一种，偶尔 $\ge$两种）。在讨论算法优劣时，只讨论基本运算的执行次数，其它的运算可以忽略不计。
如
4. 在一个表中寻找数据元素 x： x 与表中的一个项进行比较
5. 两个实矩阵的乘法： 实数的乘法（及加法）$C=AB$ 则 $c_{ij}=\sum a_{ik}{b}_{kj}$
6. 将一个数表进行排序： 表中的两个数据项进行比较

时间复杂度

用 $T(n)$ (或 $T(n,m)$ 等)来表示
渐近时间复杂性：当输入规模趋于极限情形时（相当大）的时间复杂性
7. $T(n)=O(f(n))$：若存在 $c>0$，和正整数$n_0\ge 1$，使得当 $n\ge n_0$时，总有 $T(n)\ge c\ast f(n)$。（给出了算法时间复杂度的上界，不可能比 $c\ast f(n)$ 更大）
8. $T(n)=\Omega (f(n))$：若存在 $c>0$，和正整数 $n_0\ge 1$，使得当 $n\ge n_0$ 时，存在无穷多个 $n$，使得 $T(n)\ge c\ast f(n)$成立。（给出了算法时间复杂度的下界，复杂度不可能比 $c\ast f(n)$ 更小）
9. $T(n)=\Theta (f(n))$：若存在$c_1,c_2>0$和正整数 $n_0\ge 1$，使得当 $n\ge n_0$时，总有 $T(n)\le c_1\ast f(n)$，且有无穷多个n，使得 $T(n)\ge c_2\ast f(n)$ 成立，即 $T(n)=O(f(n))$ 与 $T(n)=\Omega (f(n))$ 都成立。（既给出了算法时间复杂度的上界，也给出了下界）

多项式时间与指数时间

1. 多项式时间的算法互相之间虽有差距，一般可以接受。
2. 指数量级时间的算法对较大的 n 无实用价值

最坏时间复杂性

规模为n的所有输入中，基本运算执行次数最多的时间复杂性。
e.g.：在一个顺序表中寻找数据元素x
顺序查找：最坏情况为 $O(n)$。
二分查找：最坏情况为 $O(logn)$。

平均情况时间复杂性

规模为 $n$ 的所有输入的算法时间复杂度的平均值。
e.g.：在一个顺序表中寻找数据元素x
顺序查找：平均情况仍为 $O(n)$。
二分查找：平均情况仍为 $O(logn)$。

附录：图灵奖及历届图灵奖获得者

图灵奖于 1966 年开始设立，是 ACM（美国计算机协会）在计算机科学技术领域中所授予的最高奖项, 享
有计算机界的诺贝尔奖之美称。它是以英国的数学天才 Alan Turing 先生的名字命名的。图灵先生对早期的
计算理论与实践做出了突出的贡献。图灵奖主要授予在计算机科学技术领域做出了创造性贡献、推动了计算
机科学技术发展的杰出科学家，而这些贡献必须对计算机科学技术有长久而深远的重要影响。虽未明确规定，
授奖较偏重于计算机科学理论和软件技术方面作出贡献的科学家。
每年, 美国计算机协会将要求提名人推荐本年度的图灵奖候选人, 并附加一份 200 到 500 字的文章, 说明被
提名者为什么应获此奖。任何人都可成为提名人，美国计算机协会将组成评选委员会对被提名者进行严格的
审核，并最终确定当年的获奖者。通常每年只有 1 名获奖者, 少数的年份有 2 名(同方向), 但 02 年有 3 名。
截止到 2003 年底共发奖 38 次，共有 47 位科学家获奖。
历届图灵奖获得者名单（1966-2003）:
1966 Alan J. Perlis — PhD, MIT; Prof, Yale (was Prof at CMU) (deceased)
因在新一代编程技术和编译架构方面的贡献而获奖。ALGOL 语言和计算机科学的“催生者”。
1967 Maurice V. Wilkes — PhD, Cambridge; Prof, Cambridge
因设计、研制出世界上第一台程序实现完全在内存的存储程序式计算机 EDSAC 而获奖。
1968 Richard W. Hamming — PhD, UIUC; Prof, Naval Postgraduate School (was at Bell) (deceased)
因在计数方法、自动编码系统、检测及纠正错码方面的贡献被授予图灵奖。
1969 Marvin Minsky — PhD, Princeton, Prof, MIT
因对人工智能的贡献被授予图灵奖。创立了框架理论。有“人工智能之父”之美誉。
1970 J.H. Wilkinson — BS, Cambridge; staff, National Physical Laboratory, London
因在利用数值分析方法来促进高速数字计算机（ACE 计算机）的应用方面的研究而获奖。
1971 John McCarthy — PhD, Princeton; Prof, Stanford
因对人工智能的贡献被授予图灵奖。LISP 语言的发明人。亦有“人工智能之父”之美誉。
1972 Edsger W. Dijkstra — PhD, U Amsterdam; Prof, UT Austin
因在编程语言方面的出众表现而获奖。最先察觉到“goto 有害”。
1973 Charles W. Bachman — staff, Honeywell
因在数据库方面的杰出贡献而获奖。有“网状数据库之父”之美誉。
1974 Donald E. Knuth — PhD, Caltech; Prof, Stanford
因设计和完成 TEX(一种创新的具有很高排版质量的文档制作工具)而被授予该奖。
计算机经典巨著『计算机程序设计的艺术』的年轻作者。
1975 Allen Newell — PhD, Stanford; Prof, CMU (deceased)
和 Herbert A. Simon — PhD, Chicago; Prof, CMU (deceased)
因在人工智能、人类识别心理和表处理的基础研究而获奖。人工智能符号主义学派的创始人。
1976 Michael O. Rabin — PhD, Princeton; Prof, Harvard
和 Dana S. Scott — PhD, Princeton; Prof, CMU
因他们的论文"有限自动机与它们的决策问题"中所提出的非确定性自动机这一很有价值的概念而获奖。
1977 John Backus — BS, Columbia; staff, IBM
因对可用的高级编程系统设计有深远和重大的影响而获奖。FORTRAN 和 BNF 的发明者。
1978 Robert W. Floyd — BS, Chicago; Prof, Stanford
因其在软件编程的算法方面的影响，并开创了包括剖析理论、编程语言的语义、自动程序检验、自动程序合
成和算法分析在内的多项计算机子学科而被授予该奖。前后断言法的创始人。
1979 Kenneth E. Iverson
因对程序设计语言理论、互动式系统及发明 APL 的贡献被授予该奖。
1980 C. Anthony R. Hoare — Prof, Oxford(now at Microsoft)
因对程序设计语言的定义和设计所做的贡献而获奖。
1981 Edgar F. Codd — PhD, Michigan; staff, IBM
因在数椐库管理系统的理论和实践方面的贡献而获奖。有“关系数据库之父”之美誉。
1982 Steven A. Cook — PhD, Harvard; Prof, U Toronto
因奠定了 NP-Completeness 理论的基础而获奖。
1983 Ken Thompson — MS, Berkeley; staff, Bell-Labs
和 Dennis M. Ritchie — PhD, Harvard; staff, Bell-Labs
因在类属操作系统理论，特别是发明 C 和 UNIX 操作系统并推广而获奖。
1984 Niklaus Wirth — PhD, Berkeley; Prof, ETH Zurich
因开发了 EULER、 ALGOL-W、 MODULA 和 PASCAL 一系列崭新的计算语言而获奖。
有“结构化程序设计之父”之美誉。
1985 Richard M. Karp — PhD, Harvard; Prof, Berkeley
因对算法理论的贡献而获奖。“三栖学者”，分枝限界法的创始人。
1986 John E. Hopcroft — PhD, Stanford; Prof, Cornell
and Robert E. Tarjan — PhD, Stanford; Prof, Princeton
因在算法及数据结构的设计和分析中所取得的决定性成果而获奖。
1987 John Cocke — staff, IBM
因在面向对象的编程语言和相关的编程技巧方面的贡献而获奖。RISC 概念的首创者。
1988 Ivan E. Sutherland — PhD, MIT; staff, Sun
因在计算机图形学方面的贡献而获奖。有“计算机图形学之父”之美誉。
1989 William V. Kahan — PhD, U Toronto; Prof, Berkeley
因在数值分析方面的贡献而获奖，他是浮点计算领域的专家。有“浮点计算的先驱”之美誉。
1990 Fernando J. Corbato — PhD, MIT; Prof, MIT
因在开发大型多功能、可实现时间和资源共享的计算系统，如 CTSS 和 Multics 方面的贡献而获奖。
分时系统实现的核心人物。
1991 Robin Milner — Prof, Cambridge (was at U Edinburgh)
因在可计算的函数的逻辑(LCF)、标准元语言 ML 和并行理论(CCS)这三个方面的贡献而获奖。
1992 Butler Lampson — PhD, Berkeley; staff, Microsoft
因在个人分布式计算机系统（包括操作系统）方面的贡献而获奖。微软的首席技术官。
1993 Juris Hartmanis — PhD, Caltech; Prof, Cornell
和 Richard E. Stearns — PhD, Princeton; Prof, SUNY Albany
因奠定了计算复杂性理论的基础而获奖。
1994 Raj Reddy — PhD, Stanford; Prof, CMU
和 Edward Feigenbaum (PhD, CMU; Prof, Stanford)
因对大型人工智能系统的开拓性研究而获奖。
1995 Manuel Blum — PhD, MIT; Prof, Berkeley
因奠定了计算复杂性理论的基础和在密码术及程序校验方面的贡献而获奖。
1996 Amir Pnueli — PhD, Weizmann Institute; Prof, NYU
因在计算中引入时态（Temporal）逻辑和对程序及系统检验的贡献被获奖。
1997 Douglas Engelbart — PhD, Berkeley; staff, SRI
因提出互动式计算概念并创造出实现这一概念的重要技术而获奖。
1998 James Gray — PhD, Berkeley; staff, Microsoft
因在数据库和事务处理方面的突出贡献而获奖。
1999 Frederick P. Brooks, Jr.— PhD, Harvard; Prof, UNC
因对计算机体系结构和操作系统以及软件工程做出了里程碑式的贡献.
2000 Andrew Chi-Chih Yao — PhD, UIUC; Prof, Princeton (姚期智 now at 清华)
因对计算理论做出了诸多根本性的重大贡献. (图灵奖自创立以来获得该奖项的首位华裔学者)
2001 Ole-Johan Dahl, and Kristen Nygaard — Profs, U Oslo
因他们在设计编程语言 SIMULA I 和 SIMULA 67 时产生的基础性想法,这些想法是面向对象技术的肇始.
2002 Ronald L. Rivest, Adi Shamir, Leonard M. Adelman —Ronald L. Rivest: PhD, Stanford; MIT
Adi Shamir: PhD, Weizmann; Weizmann；Leonard M. Adelman: PhD, Berkeley; USC
因他们在公共密匙算法上所做的杰出贡献(RSA 算法是当前在互联网传输、银行以及信用卡产业中被广泛
使用的安全基本机制).
2003 Alan Kay — PhD, Utah; HP Labs (was at Xerox PARC)
因发明第一个完全面向对象的动态计算机程序设计语言 Smalltalk.
2004 Vinton G. Cerf & Robert E. Kahn
For pioneering work on internetworking, including the design and implementation of the Internet’s basic communications protocols,
TCP/IP, and for inspired leadership in networking.
最高学历毕业学校：Berkeley 6 人，Princeton、Stanford 各 5 人，Harvard、MIT 各 4 人，Cambridge、UIUC、
Caltech 、Chicago、Weizmann Institute 各 2 人，Amsterdam、CMU、Columbia、Michigan、Toronto、Utah
各 1 人