Question

大O表示法的算法的执行时间

Answer 1

算法的执行时间等于它所有基本操作执行时间之和， 而一条基本操作的执行时间等于它执行的次数和每一次执行的时间的积，
如下：
算法的执行时间 = 操作1 + 操作2 + ... + 操作n
操作的执行时间 = 操作执行次数 X 执行一次的时间
然而存在一个问题，不同的编程语言，不同的编译器，或不同的CPU等因素将导致执行一次操作的时间各不相同，这样的结果会使算法的比较产生歧义， 于是我们假定所有计算机执行相同的一次基本操作所需时间相同，而把算法中基本操作所执行的最大次数作为量度。就是说我们把算法的执行时间简单地用基本操作的执行次数来代替了。
那么除此之外，基本操作是什么？ 它可以是基本运算，赋值，比较，交换等，如在排序中，基本操作指的是元素的比较及交换。而在线性查找中，它是数据的比较。
时间复杂度和大O表示法
当问题规模即要处理的数据增长时， 基本操作要重复执行的次数必定也会增长， 那么我们关心地是这个执行次数以什么样的数量级增长。所谓数量级可以理解为增长率。这个所谓的数量级就称为算法的渐近时间复杂度（asymptotic time complexity）， 简称为时间复杂度。如何分析这个数量级呢？ 由于基本操作的执行次数是问题规模n 的一个函数T(n）， 所以问题就是我们要确定这个函数T(n）是什么， 然后分析它的数量级， 拥有相同数量级的函数 f(n) 的集合表示为 O(f(n））， O是数量级的标记。如果T(n）的数量级和f(n）相同，
显然T(n) ∈ Of(n）。这个函数的值表示当我要处理的数据量增长时，基本操作执行次数以什么样的比例增长。即n增长时，T(n）增长多少？