如何确定代码的精确时间复杂度？附USACO代码及优化疑问

1. 代码的精确时间复杂度 #

你的代码时间复杂度为 O(n² + n log n)，核心构成：

• list.sort()：Python内置排序采用Timsort算法，时间复杂度是O(n log n)
• 嵌套两层for循环：外层循环执行n次，内层每次也执行n次，这部分复杂度为O(n²)

时间复杂度取最高阶项，最终等价于O(n²)，和题目预期解法的复杂度一致，不会比预期解法慢——对于n≤1000的限制，O(n²)最多产生1e6次操作，完全在Python的运行时间范围内。

2. 关于O(n²+O(1))的疑问 #

时间复杂度写法里，O(n² + O(1))等价于O(n²)，因为当n增大时，常数项的影响可以忽略不计。针对n≤1000的测试用例，这种复杂度的代码完全能通过测试，不用额外担心常数项的问题。

3. 优化至线性时间（近似O(n)）的方法 #

你的代码核心需求是：在排序后的数组中，统计每个元素list[j]对应的、满足list[j] ≤ list[i] ≤ list[j]+k的元素个数，再取最大值。利用数组已排序的特性，可以用双指针法将核心统计逻辑优化到O(n)：

优化后的代码示例：

import random

def generatek():
    return 3

n = int(input("Enter the amount of diamonds Bessy has: (up to 1000) "))
if n > 1000:
    exit("Bozo follow instructions")

# 简化随机数组生成
diamonds = [random.randint(0, 10000) for _ in range(n)]
diamonds.sort()

k = generatek()
max_count = 0
right = 0

for left in range(n):
    # 右指针持续右移，直到不满足条件
    while right < n and diamonds[right] <= diamonds[left] + k:
        right += 1
    # 当前窗口内的元素数量为right - left
    current_count = right - left
    if current_count > max_count:
        max_count = current_count

print(diamonds)
print(f"k was {k}")
print(f"highest amount of diamonds bessy can hold is {max_count}")

优化思路说明 #

• 数组已排序，每个左指针left对应的右指针right只会向右移动，不会回溯
• 整个过程中left和right各遍历数组一次，核心统计逻辑为O(n)；加上排序的O(n log n)，整体复杂度为O(n log n)——如果题目输入的数组本身有序，就能达到纯O(n)的时间复杂度。

额外代码建议 #

• 不要用list作为变量名，会覆盖Python内置的list类型
• 生成随机数组可以用列表推导式替代while循环，更简洁高效

内容的提问来源于stack exchange，提问作者user23238312