被调用函数的大O表示法的时间复杂度

Question

我阅读了许多关于计算time complexity O(n)的资源。我把我所理解的应用到我的代码中。

下面是我的代码和我试图找到time complexity。

我代码:

float Euclidean_distance(int array_point_A[20], int  array_point_B[20]) {
float sum = 0.0;
float  w[20] = { 0.0847282, 0.0408621, 0.105036, 0.0619821, 0.0595455, 0.0416739, 0.0181147, 0.00592921,
0.040049, 0.0766054, 0.0441091, 0.0376111, 0.0124285, 0.0733558, 0.0587338, 0.0303001, 0.0579207, 0.0449221,
0.0530462, 0.0530462 };
for (int i = 0; i < 20; ++i) {
float a = array_point_A[i] - array_point_B[i];
float wieghted_distance = w[i] * (a * a); 
sum += wieghted_distance;
}
return sqrt(sum);
}

int KNN_classifier(int X_train[4344][20], int Y_train[4344], int k, int data_point[20]) {
// Calculate the distance between data_point and all points.    
float array_dist[4344]{};
int index_arr[4344]{} 
for (int i = 0; i *< 4344; ++i) {
array_dist[i] = Euclidean_distance(X_train[i], data_point);
index_arr[i] = i;
}

现在:功能Euclidean_distance有2 operations outside the loop和3 operations inside the loop that will iterate 20 times。因此，2+3n，然后我们有O(n)。

现在:对于函数KNN_classifier。它有一个循环，将迭代4344次。在循环中，有2 operations。所以我们有2n和O(n)。//我不确定这个解决方案。

这个操作array_dist[i] = Euclidean_distance(X_train[i], data_point);混淆了我。所以，我需要在我的计算中包括Euclidean_distance时间复杂度吗?如果是这样，我猜时间复杂度将是O(n^2)。但是这两个循环的边界不同。

我需要帮助!!

Answer 1

Big-O表示法只对一个或多个参数有意义，但是您还没有描述代码中哪些值是变量，哪些是常量。

如前所述，函数KNN_classifier实际上是O(1，因为4344是一个固定常量，而20是一个常量。如果20是一个常量，并且X_train和Y_train的大小打算作为某个数字n变化，那么它就是O(n)。如果常数20也变化为m，那么它就是O(n*m)。