Как да определим времевата сложност на функция, която търси първия елемент в масив, който липсва в друг?

За да определите времевата сложност на функция, която търси първия елемент в масива A, който липсва в масива B, трябва да анализирате алгоритъма:

1. Ако за всеки елемент от масива A проверяваме наличието му в масива B чрез линейно търсене (например, с цикъл), тогава за всеки елемент от A правим търсене в B — това е O(n) за всеки елемент, където n е размерът на масива B. Ако размерът на A е m, тогава общата сложност ще бъде O(m * n).

2. Ако вместо това създадем структура от данни за бързо търсене, като HashSet от елементите на масива B (в O(n)), проверката за наличие на елемент ще бъде средно O(1). Тогава цялата алгоритъм ще бъде:

• Създаване на HashSet от масива B — O(n)
• Обхождане на елементите на масива A и проверка за наличие в HashSet — O(m)

Общата времева сложност е — O(m + n).

Пример на Kotlin:

fun findFirstMissing(a: List<Int>, b: List<Int>): Int? {
    val setB = b.toHashSet() // O(n)
    for (element in a) { // O(m)
        if (element !in setB) {
            return element
        }
    }
    return null
}

Така, времевата сложност зависи от реализацията и може да варира от O(m * n) до O(m + n).