Построение алгоритма сложности времени O (n) для поиска значения в двух массивах - PullRequest
Новая
       34

Построение алгоритма сложности времени O (n) для поиска значения в двух массивах

0 голосов
/ 11 апреля 2011

Скажем, у меня есть 2 массива int, отсортированных по возрастанию. и я пытаюсь найти, есть ли значение из массива A, совпадающее со значением в массиве B, при этом временная сложность Big-O равна n. Сначала я думал о линейном поиске, но это было невозможно, потому что мне нужен был вложенный цикл for. Моя другая идея - попытаться использовать бинарный поиск и добавить к нему цикл for. Будет ли это работать?

Так как ... 

for (int i = 0;i<B.length(), i++) {
   BinarySearch(A[0..N-1], value, low, high) {
       if (high < low)
           return -1 // not found
       mid = low + (high - low) / 2
       if (A[mid] > value)
           return BinarySearch(A, value, low, mid-1)
       else if (A[mid] < value)
           return BinarySearch(A, value, mid+1, high)
       else
           return mid // found
   }
}

это не полный код, я просто скопировал его из вики в качестве примера. Я иду в правильном направлении?

Ответы [ 3 ]

1 голос
/ 11 апреля 2011

Вы говорите, что массивы отсортированы уже.Это очень важное условие, с которым вы должны работать.Затем у вас есть две последовательности:* и <B в моем примере.Остальное - просто целочисленные сравнения.Это приведет к сложности времени O(Max(a.Length, b.Length)) (следовательно, O(n)).

Возможное улучшение: Вначале выясните, имеет ли смысл вообще обходить входы.если действительно оставить как домашнее задание.

0 голосов
/ 12 апреля 2011

Объединить оба списка, объединение - O (n).

Процедура слияния будет:

1) Сравните «наименьший элемент» обоих списков, если они равны, это формирует наш ответ. 2) Если нет, удалите меньшее из двух из списка и обновите список. 3) Повторите 1) и 2), пока не закончится любой из списка.

сложность будет Min (a.length, b.length), которая может быть O (1) также, если один массив сравнительно очень мал, чем другой.

0 голосов
/ 11 апреля 2011

пример кода, чтобы показать, как Python говорит само за себя;) 

def find_first_matching_value(array_a, array_b):
    "Return the first value in both arrays"
    # both arrays are sorted
    assert sorted(array_a) == array_a
    assert sorted(array_b) == array_b
    array_a_index = 0
    array_b_index = 0
    while (array_a_index < len(array_a)
           and array_b_index < len(array_b)):
        if array_a[array_a_index] > array_b[array_b_index]:
            # skip to next element in array b
            array_b_index += 1
        elif array_a[array_a_index] < array_b[array_b_index]:
            # skip to next element in array a
            array_a_index += 1
        else:
            # found
            return array_a[array_a_index]
...