C 帮助锻炼

Question

“编写一个算法，给定两个大小为 N 的有序 vector ，以有序的方式打印出现在两个 vector 上的所有元素。在最坏的情况下，程序的执行时间必须与 N 成正比。”

在本练习中，我将执行一个循环来检查数组 a[] 中的每个数字，然后使用二分搜索算法检查数组 b[] 并比较它是否等于 a[] 上的数组.

但我不知道在最坏的情况下是否与 N 成正比。

int main() {
    int a[6] = {2, 8, 15, 31, 46, 75};
    int b[6] = {1, 8, 17, 21, 31, 75};
    int i, tam = 6, key, res, c[6], k=0;

    for (i = 0; i < tam; i++) {
        key = a[i];
        res = binary_search(b, tam, key);
        if (res != -1) {
            c[k]=a[i];
            k++;
        }
    }

    return 0;
}

int binary_search(int a[], int n, int key) {
    int low = 0, high = n - 1;

    while (low <= high) {
        int mid = (low + high) / 2;

        if (key < a[mid])high = mid - 1;
        else if (key > a[mid]) low = mid + 1;
        else return mid;
    }
    return -1;
}

Answer 1

But I don't know if on the worst case is proportional to N.

事实并非如此。对有序列表进行二分查找的时间复杂度为 O(log n)。如果您必须对其中一个数组中的所有元素执行此操作，那么您需要的时间复杂度为 O(n log n)。

当您尝试在 O(n) 时间内解决问题并且当前的解决方案为 O(n log n) 时，解决方案中花费 O(log n) 的部分可能就是问题所在。