如何以O(n)时间复杂度计算n个进程的总周转时间

可以利用树状数组（Fenwick Tree）维护前缀和，将时间复杂度优化到O(n log M)，其中M是进程运行时长的最大值（这里M=1e4），完全满足n=1e5的约束。

问题分析 #

根据你推导的周转时间公式，总周转时间由三部分组成：

1. 所有进程的总运行时间 total_T（直接求和即可）
2. S2 = sum_{i} sum_{j<i} min(T[j], T[i])：每个进程i等待前面进程j的时间之和
3. S3 = sum_{i} sum_{j>i} min(T[j], T[i]-1)：每个进程i等待后面进程j的时间之和

核心难点是高效计算sum(min(a, b))这类前缀/后缀求和，由于T[i]的范围仅为1~1e4，我们可以用树状数组快速维护和查询前缀的数量与总时长，从而在O(log M)时间内完成单次求和计算。

具体实现步骤 #

1. 计算总运行时间total_T

直接遍历数组求和，时间复杂度O(n)。

2. 计算S2（前缀min求和）

使用两个树状数组：

• ft_count：维护前缀中各时长进程的数量的前缀和
• ft_total：维护前缀中各时长进程的总运行时间的前缀和

遍历每个进程i时：

• 查询前缀中时长≤T[i]的进程总数量sum_cnt和总时长sum_total
• 前缀中所有进程对i的等待时间为：sum_total + T[i]*(当前前缀总数量 - sum_cnt)
• 将该值累加到S2，然后更新树状数组，把当前进程的时长加入前缀。

3. 计算S3（后缀min求和）

同样使用两个树状数组，遍历每个进程j时，计算前面所有进程i<j对j的贡献（等价于原问题中i等待j的时间）：

• 利用等式min(T[j], T[i]-1) = min(T[j]+1, T[i]) - 1，将问题转化为计算前缀min(T[j]+1, T[i])的和，再减去前缀进程数量
• 计算方式类似S2，将结果累加到S3，然后更新树状数组。

4. 总周转时间

总周转时间 = total_T + S2 + S3

代码实现（Python） #

class FenwickTree:
    def __init__(self, size):
        self.n = size
        self.tree = [0]*(self.n + 1)
    
    def update(self, idx, delta):
        # idx从1开始
        while idx <= self.n:
            self.tree[idx] += delta
            idx += idx & -idx
    
    def query(self, idx):
        # 查询1~idx的前缀和，idx从1开始，若idx=0返回0
        res = 0
        while idx > 0:
            res += self.tree[idx]
            idx -= idx & -idx
        return res

def calculate_total_turnaround(T):
    max_T = 10**4
    total_T = sum(T)
    n = len(T)
    
    # 计算S2
    ft_count = FenwickTree(max_T)
    ft_total = FenwickTree(max_T)
    S2 = 0
    current_count = 0
    for x in T:
        sum_cnt = ft_count.query(x)
        sum_total = ft_total.query(x)
        sum_min = sum_total + x * (current_count - sum_cnt)
        S2 += sum_min
        ft_count.update(x, 1)
        ft_total.update(x, x)
        current_count += 1
    
    # 计算S3
    ft_count = FenwickTree(max_T)
    ft_total = FenwickTree(max_T)
    S3 = 0
    current_count = 0
    for x in T:
        # 计算sum(min(x, t-1)) = sum(min(x+1, t)) - current_count
        query_x = x + 1
        if query_x > max_T:
            query_x = max_T
        sum_cnt = ft_count.query(query_x)
        sum_total = ft_total.query(query_x)
        sum_min_x1 = sum_total + query_x * (current_count - sum_cnt)
        sum_min = sum_min_x1 - current_count
        S3 += sum_min
        ft_count.update(x, 1)
        ft_total.update(x, x)
        current_count += 1
    
    return total_T + S2 + S3

# 示例测试
T = [3,1,2]
print(calculate_total_turnaround(T))  # 输出13

复杂度分析 #

• 时间复杂度：每个进程的查询和更新操作都是O(log M)，M=1e4，因此总时间为O(n log M)，对于n=1e5来说完全可行。
• 空间复杂度：树状数组的大小为O(M)，即1e4级别，空间占用极小。

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