如何判断算法性能优劣？求通用评估方法与最优算法选择方案

作为开发社区新手，我想了解是否存在通用方法或函数来判断算法性能优劣，进而选择最优算法。目前我使用装饰器统计函数执行耗时，但认为该方法不具备外推性，特求助合适的方案。以下是我使用time库统计两个数组负数计数函数耗时的示例代码：

计时装饰器代码 #

import time

def time_it(func):
    def wrapper(*args,**kwargs):
        start=time.time()
        result=func(*args,**kwargs)
        end=time.time()
        print(func.__name__ +" took "+str((end-start)*1000)+" mil seconds")
        return result
    
    return wrapper

测试代码 #

array=[
    [-4, -3, -1, 1],
    [-2, -2, 1, 2],
    [-1, 1, 2, 3],
    [1, 2, 4, 5]
]

@time_it
def count_negatives(array):
    count=0
    for i in array:
        for j in i:
            if j < 0:
                count +=1
    return count

@time_it
def count_neg(array):
    count=0
    row=0
    column=0
    while row<len(array) and column<len(array[0]):
        if array[row][column]<0:
            count +=1
            column +=1
        else:
            row +=1
            column=0
    return count


print(count_negatives(array))
print(count_neg(array))

通用判断方案 #

1. 渐近时间/空间复杂度分析

这是判断算法性能最核心的通用方法，通过分析输入规模趋近无穷时的资源消耗趋势，能直接对比不同算法的本质效率，不受测试环境干扰：

• 时间复杂度：用大O符号（如O(n)、O(m*n)、O(m+n)）表示。比如count_negatives是双层循环，时间复杂度为O(m*n)（m是行数，n是列数）；count_neg的逻辑依赖数组结构，最坏情况也是O(m*n)，但如果数组每行是前负后正的有序结构，可优化为O(m+n)的高效算法（见下文示例）。
• 空间复杂度：衡量算法运行时占用的额外内存。你的两个函数都只用到几个计数变量，空间复杂度为O(1)。

2. 多轮基准测试

单次计时受系统负载、进程调度影响大，多轮运行取平均能得到更可靠的结果，Python内置的timeit模块可实现：

import timeit

# 定义无装饰器的测试函数
def count_negatives(array):
    count=0
    for i in array:
        for j in i:
            if j < 0:
                count +=1
    return count

def count_neg(array):
    count=0
    row=0
    column=0
    while row<len(array) and column<len(array[0]):
        if array[row][column]<0:
            count +=1
            column +=1
        else:
            row +=1
            column=0
    return count

# 测试数据
array=[
    [-4, -3, -1, 1],
    [-2, -2, 1, 2],
    [-1, 1, 2, 3],
    [1, 2, 4, 5]
]

# 每个函数运行10000次，输出平均耗时
print("count_negatives 平均耗时:", timeit.timeit(lambda: count_negatives(array), number=10000))
print("count_neg 平均耗时:", timeit.timeit(lambda: count_neg(array), number=10000))

3. 分场景测试（最坏/最好/平均）

不同算法在不同输入下表现差异大，需覆盖多种测试用例：

• 最好情况：输入数组全为正数，count_neg会直接退出循环，耗时极短；count_negatives仍需遍历所有元素。
• 最坏情况：输入数组全为负数，两个函数都要遍历所有元素。
• 平均情况：接近真实业务的随机输入。

4. 针对有序数组的优化算法

如果数组每行是非递减有序（前负后正），可使用O(m+n)的高效算法：

def count_neg_optimized(array):
    count = 0
    rows = len(array)
    if rows == 0:
        return 0
    cols = len(array[0])
    row = 0
    col = cols - 1
    while row < rows and col >= 0:
        # 当前元素为负，说明该行从0到col都是负数
        if array[row][col] < 0:
            count += col + 1
            row += 1
        else:
            # 当前元素非负，往左寻找更小的列
            col -= 1
    return count

该算法从右上角开始遍历，每次要么下移一行，要么左移一列，最多遍历m+n次，效率远高于双层循环。

内容的提问来源于stack exchange，提问作者Anthony J. B.