包含函数调用的代码Big O时间复杂度计算相关问题

1. 先纠正Euclidean_distance的复杂度判断 #

你写的Euclidean_distance函数中，循环迭代次数固定为20，属于常数级别的固定开销，所以这个函数的时间复杂度是O(1)（常数时间）。
如果把特征维度d作为可变参数（而非硬编码为20），这个函数的复杂度是O(d)，这里的特征维度和后续KNN中的训练集规模是两个完全独立的参数，不要混淆。

2. KNN_classifier的复杂度计算规则 #

首先明确：计算函数时间复杂度时，必须把内部调用的其他函数的时间开销纳入计算，这是复杂度分析的基本规则。
接下来分两种场景讨论：

场景1：所有参数为代码中写死的固定值 #

你的代码中特征维度固定为20、训练集大小固定为4344，所有循环的迭代次数都是固定常数，所以你贴出的这部分KNN代码时间复杂度是O(1)。

场景2：通用算法场景，将训练集大小N、特征维度d作为可变参数 #

• 单次Euclidean_distance调用开销：O(d)
• 计算所有训练样本距离的循环执行N次，所以这部分总开销是O(N*d)

你之前误以为会变成O(n²)，核心问题是你把两个独立的可变参数（特征维度d、训练集规模N）都用同一个变量n指代了，实际上二者没有关联，所以复杂度是两个参数的乘积，而非单参数的平方。
如果特征维度是固定值（比如你代码里硬编码为20），那么d可以视为常数系数直接省略，这部分的复杂度就是O(N)，你之前得出的复杂度结果是对的，只是推导过程没有考虑内部函数调用的开销，不过因为内部开销是常数，所以没有影响最终的复杂度结论。

补充说明 #

你贴出的KNN代码只完成了距离计算的部分，完整的KNN实现还需要对距离数组排序、取Top K近邻、类别投票三个步骤，其中排序的通用时间复杂度是O(N log N)，如果N的规模远大于d，那么排序的开销会成为整个KNN算法的瓶颈，整体复杂度为O(N log N)。

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