大o计算法

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

在评估算法性能时，我们通常关注的是其执行时间，这是通过所有基本操作的执行时间和次数来计算的。基本操作，如基本运算、赋值、比较和交换，构成了算法的核心步骤。例如，在排序中，比较和交换是基本操作；而在线性查找中，数据的比较是关键步骤。

然而，实际的执行时间会受到多种因素影响，如编程语言、编译器和CPU。为了解决这种歧义，大O表示法（O-notation）引入了一个假设，即所有计算机对相同基本操作的执行时间是可比的。我们关注的是算法在最坏情况下的基本操作次数，即当问题规模（例如处理的数据量）n增长时，这些操作的最大执行次数。

时间复杂度，或渐近时间复杂度，是对算法执行时间随着问题规模增长的长期行为的描述。它关注的是基本操作执行次数的增长率，用一个函数T(n)表示，其中n是问题规模。我们通过确定T(n)的函数形式，然后分析其数量级，即其增长的速度或规模。具有相同数量级的函数集合用O(f(n))表示，其中f(n)是基准函数。如果T(n)和f(n)在增长速度上相似，我们可以说T(n)属于O(f(n))。

换句话说，大O表示法帮助我们理解，当数据量n增大时，算法执行时间将以何种比例增加，这是衡量算法效率的重要指标。

大O表示法：称一个函数g(n)是O(f(n))，当且仅当存在常数c>0和n0>=1，对一切n>n0均有|g(n)|<=c|f(n)|成立，也称函数g(n)以f(n)为界或者称g(n)囿于f(n)。记作g(n)=O(f(n))。 定义：如果一个问题的规模是n，解这一问题的某一算法所需要的时间为T(n)，它是n的某一函数。T(n)称为这一算法的“时间复杂度”。当输入量n逐渐加大时，时间复杂度的极限情形称为算法的“渐近时间复杂度”。