Бір массивте бар болса да, екіншісінде жоқ бірінші элементті табатын функцияның уақыттық күрделілігін қалай анықтауға болады?

A array A-дан бірінші жетіспейтін элементті табу функциясының уақыттық күрделілігін анықтау үшін алгоритмді талдау керек:

1. Егер A-ның әрбір элементі үшін оның B-да бар-жоғын қайталау арқылы тексерсеңіз (мысалы, цикл арқылы), онда әрбір элемент үшін B-да іздеу жүргізіледі — бұл O(n) уақыт, мұнда n — B-ның өлшемі. Егер A-ның өлшемі m болса, жалпы күрделілік O(m * n).

2. Егер алдын ала B-дан жылдам іздеу үшін құрылым жасасаңыз, мысалы, B элементтерінен HashSet құрып (O(n)), онда элементтің бар-жоғын тексеру орташа есеппен O(1). Сонда жалпы алгоритм:

• B-дан HashSet құру — 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)-ге дейін өзгеруі мүмкін.