被调用函数的 Big 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).

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

Time complexity with Big O notation for a called function

c++

time-complexity

knn