时间复杂度怎么算例题

在进行算法分析时，语句总的执行次数T(n)是随问题规模n变化的函数，我们通过分析T(n)随n的变化来确定其数量级。算法的时间复杂度，即算法的时间度量，记作：T(n)=O(f(n))。它表示随着问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，被称为算法的渐进时间复杂度，简称时间复杂度。

我们来看顺序结构的时间复杂度。以利用高斯定理计算1到n的和的算法为例，其运行次数函数为f(n)=3。按照推导大O阶的方法，第一步将常数项3改为1；在保留最高阶项时，发现没有最高阶项，因此该算法的时间复杂度为O(1)。这种与问题的大小无关、执行时间恒定的算法被称为具有O(1)的时间复杂度，即常数阶。对于单纯的分支结构，无论真假，执行的次数都是恒定的，不会随n的增大而发生变化，所以其时间复杂度也是O(1)。

线性阶的循环结构相对复杂。要确定某个算法的阶次，需要确定特定语句或语句集的运行次数。分析算法复杂度的关键是分析循环结构的运行情况。

以下是一段循环代码的时间复杂度分析。由于每次count乘以2后，距离n的距离就更近了一分，所以循环的次数是由2^x=n得出x=logn决定的。这个循环的时间复杂度为O(logn)。

对于循环嵌套的情况，我们需要分别分析内循环和外循环的时间复杂度。如果外循环的循环次数变为m，则时间复杂度变为O(mXn)。循环的时间复杂度等于循环体的复杂度乘以该循环的运行次数。

还有常见的三重循环嵌套的情况，其时间复杂度为O(n^3)。常见的时问复杂度从小到大包括：O(1)、O(logn)、O(n)、O(n^2)、O(n^3)等。过大的n值如O(2^n)和O(n!)等可能导致结果不现实。在实际应用中，我们更关注最坏情况运行时间，因为这是运行时间的保证。平均运行时间也有实际意义，因为它是期望的运行时间。但在没有特殊说明的情况下，一般指的是最坏时间复杂度。

在编写代码时，我们可以用空间来换取时间。例如，通过建立一个数组来存储年份信息，将判断年份是否为闰年的问题转化为查找数组中的值的问题，从而最小化运算。算法的空间复杂度通过计算算法所需的存储空间来实现，其计算公式为S(n)=O(f(n))。其中，n为问题规模，f(n)为语句关于n所占存储空间的函数。若算法执行时所需的辅助空间相对于输入数据量而言是常数，则空间复杂度为O(1)。通常我们使用的“复杂度”指的是时间复杂度。

对于含有多个参数的算法，其时间复杂度的计算可能会更复杂。例如：T(n,m) = T1(n) + T2(m) = O(max{f(n), g(m)}) 或 T(n,m) = T1(n) T2(m) = O(max{f(n)g(m)})。这些公式可以帮助我们理解算法时间复杂度与参数之间的关系。