U134446 LMOI-Time 时间复杂度#4

在计算机科学中，时间复杂性，又称时间复杂度，算法的时间复杂度是一个函数，它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大 $O$ 符号表述，不包括这个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被称为是渐近的，亦即考察输入值大小趋近无穷时的情况。 为了计算时间复杂度，我们通常会估计算法的操作单元数量，每个单元运行的时间都是相同的。因此，总运行时间和算法的操作单元数量最多相差一个常量系数。 相同大小的不同输入值仍可能造成算法的运行时间不同，因此我们通常使用算法的最坏情况复杂度，记为 $T(n)$，定义为任何大小的输入 $n$ 所需的最大运行时间。另一种较少使用的方法是平均情况复杂度，通常有特别指定才会使用。时间复杂度可以用函数 $T(n)$ 的自然特性加以分类，举例来说，有着 $T(n) =O(n)$ 的算法被称作“线性时间算法”；而 $T(n) =O(M^n)$ 和 $M= O(T(n))$ ，其中 $M≥n> 1$ 的算法被称作“指数时间算法”。 一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为 $T(n)$。 一般情况下，算法中基本操作重复执行的次数是问题规模 $n$ 的某个函数，用 $T(n)$ 表示，若有某个辅助函数 $f(n)$,使得当 $n$ 趋近于无穷大时，$\frac{T(n)}{f(n)}$的极限值为不等于零的常数，则称 $f(n)$ 是 $T(n)$ 的同数量级函数。记作 $T(n)=O(f(n))$, 称 $O(f(n))$ 为算法的渐进时间复杂度，简称时间复杂度。 在各种不同算法中，若算法中语句执行次数为一个常数，则时间复杂度为 $O(1)$, 另外，在时间频度不相同时，时间复杂度有可能相同，如 $T(n)=n^2+3n+4$ 与 $T(n)=4n^2+2n+1$ 它们的频度不同，但时间复杂度相同，都为 $O(n^2)$。 介绍了这么多，大家可能已经明白本此比赛的目的：卡时间复杂度。因此，每道题都会设有 `O2优化` 标签。 ------------ 这题远比第三题简单。

假设亚特兰蒂斯中一共有 $N$ 幢建筑排成一条线，每幢建筑的高度 $h_i$ 各不相同。初始时，小马斯可以在任何一幢建筑的顶端。他可以选择一个方向飞，但是不能中途改变方向（因为亚特兰蒂斯变幻莫测，且小马斯急着回家）。因为小马斯不可能会飞，他只能往下滑行（即：只能从较高的建筑滑翔到较低的建筑）。他希望尽可能多地经过不同建筑的顶部，这样可以减缓下降时的冲击力，减少受伤的可能性。请问，他最多可以经过多少幢不同建筑的顶部（包含初始时的建筑）？

无

无

范围如题。