1. 请给出 T (n) 尽可能紧凑的渐进上界并予以说明。


    答案：

    说明：对于任意，存在，则可以得出。


    答案：

    说明：对于任意，存在，则可以得出或，其中。


    答案：

    说明：对于任意，存在，则可以得出，进一步可以得到。


    答案：

    说明：对于任意，存在，则可以得出，其中。


    答案：

    说明：对于任意，存在，则可以得出。


    答案：

    说明：对于任意，存在，则可以得出。


    答案：

    说明：对于任意，存在。

  2. 游戏获奖问题

    在一场射击比赛中，有名选手参加比赛，每名选手的得分都不同，记为，其中第名选手的得分为，且对于任意的有。按照比赛规则，分数排名为前的选手可以获得与其得分相等的奖金（包括第名）。
    例如，当有名选手参加比赛，得分为时，排名位于前 的选手得分为 ，则主办方应该发放奖金元。
    请你设计一个算法，计算这次比赛主办方一共要发放多少奖金。请描述算法的核心思想，给出算法伪代码并分析其对应的时间复杂度。

    解：

    该问题即求数组最大的个元素求和值为多少。将数组从大到小按照顺序排序，选取头部个元素求和即可。

    伪代码如下，时间复杂度在：

    Q2

  3. 奇数因子和问题

    定义 为整数的最大奇数因子，例如，。
    请 你 设 计 一 个 高 效 算 法， 计 算 一 个 整 数 区 间内 所 有 数 的 最 大 奇 数 因 子 和， 即。请描述算法的核心思想，给出算法伪代码并分析其对应的时间复杂度。例如，区间的计算结果为。

    解：

    该问题即求出在间的整数的最大奇数因子，并将其求和。对于奇数，最大奇因子就是其本身；对于偶数，则应不断对其除以2，直至剩余值不再整除2为止，此时该值即为该数的最大奇因子。

    伪代码如下，时间复杂度在：s

    Q3

  4. 施工点对计数问题

    在一个城市的修建工程中，有个施工点，其中表示第个施工点的成本。
    为完成任务，工程师们需要选择两个不同的施工点进行联合施工，联合施工的成本为每个施工点的成本加和，并且需要保证联合施工的总成本不能超过预算上限。形式化地说：需要计算所有满足预算限制的施工点对的数量，其中且。
    请你设计并实现一个算法来解决该问题，描述算法的核心思想，给出算法伪代码并分析其对应的时间复杂度。

    解：

    该问题即求出数组中满足条件的元素组数量，且该元素组内是有顺序的。遍历数组内全部元素，计算两两加和数值，判断其与l的关系，若满足条件，则施工点对数量加一。

    伪代码如下，时间复杂度在：

    Q4

  5. 最近村庄距离问题

    在一个广阔的平原上，有个村庄。每个村庄都有一个独特的位置，记为，表示在平面上横纵坐标的位置。现在，政府打算优先在两个距离最接近的村庄之间修建一条公路，以便加强它们之间的交通联系，其中村庄之间的距离定义为欧几里得距离，即对于两个村庄和，它们之间的距离为：。
    请你设计一个高效算法，计算在平原上距离最近的两个村庄之间的距离。请描述算法的核心思想，给出算法伪代码并分析其对应的时间复杂度。

    解：

    该问题即计算任意两个点之间的的距离，并求这些距离之中的最小值。建立一个最小值，初始值设为无穷。遍历村庄，获得任意两个村庄之间的距离，并与最小值比较，若小于最小值，则更新最小值。

    伪代码如下，时间复杂度在：

    Q5