如何计算Python文件分类程序的时间复杂度？如何优化该程序？

一、当前代码的时间复杂度 #

拆解每一步的耗时情况：

1. 过滤文件夹：遍历列表时用files.pop(files.index(file))，index查找元素是O(n)操作，列表中间删除元素也是O(n)，这一步整体时间复杂度为O(n²)（n是初始文件+文件夹的总数）。
2. 收集扩展名：遍历过滤后的m个文件，每次判断extention not in extentions是O(k)操作（k是已收集的扩展名数量），最坏情况每个文件扩展名都不同，这一步时间复杂度是O(m²)。
3. 按扩展名归类：外层遍历k个扩展名，内层遍历m个文件，最坏情况k=m，这一步时间复杂度是O(m²)。

整体时间复杂度为O(n²)（因为n≥m，高阶项主导）。

二、优化方案：将复杂度降至O(n) #

核心思路是通过一次遍历完成所有操作，避免嵌套循环和低效查找。

优化后的代码 #

from os import path, listdir
import shutil

def main():
    grouped = {}
    # 一趟遍历完成过滤+归类
    for item in listdir():
        if path.isdir(item):
            continue
        # 处理无扩展名的文件（比如README这类无后缀的文件）
        ext = item.split(".")[-1] if "." in item else "无扩展名"
        # 字典键查找是O(1)，直接维护归类列表
        if ext not in grouped:
            grouped[ext] = []
        grouped[ext].append(item)
    
    print("过滤后的文件:", [file for lst in grouped.values() for file in lst])
    print("所有扩展名:", list(grouped.keys()))
    print("归类结果:", grouped)

if __name__ == '__main__':
    main()

优化细节 #

• 一次遍历完成所有操作：不再分三步处理，每个项目只遍历一次，时间复杂度直接降到O(n)。
• 替换低效操作：用字典的O(1)键查找替代列表的O(k)查找，去掉pop(index)这种O(n)的删除操作，改用跳过文件夹的方式过滤。
• 兼容无扩展名文件：原代码会把无扩展名的文件名当作扩展名，优化后统一归到“无扩展名”分类，逻辑更合理。

额外功能补充（可选） #

如果需要自动创建文件夹并移动文件，在main函数末尾添加以下代码：

# 创建对应文件夹并移动文件
for ext, files in grouped.items():
    folder_path = f"{ext}_文件"
    if not path.exists(folder_path):
        mkdir(folder_path)
    for file in files:
        shutil.move(file, path.join(folder_path, file))

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