Kā noteikt funkcijas laika sarežģītību, kas meklē pirmo elementu masīvā, kas nav citā?

Lai noteiktu funkcijas laika sarežģītību, kas meklē pirmo elementu masīvā A, kas nav masīvā B, ir jāanalizē algoritms:

1. Ja katram elementam no masīva A pārbaudām tā esamību masīvā B ar lineāru meklēšanu (piemēram, ar ciklu), tad katram A elementam veicam meklēšanu B — tas ir O(n) katram elementam, kur n ir masīva B lielums. Ja A lielums ir m, tad kopējā sarežģītība būs O(m * n).

2. Ja vietā, lai to darītu, izveidojam datu struktūru ātrai meklēšanai, piemēram, HashSet no masīva B elementiem (par O(n)), tad pārbaude par elementa esamību būs vidēji O(1). Tad kopējais algoritms būs:

• Izveidot HashSet no masīva B — O(n)
• Pārlūkot masīva A elementus un pārbaudīt to esamību HashSet — O(m)

Kopējā laika sarežģītība — O(m + n).

Piemērs 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
}

Tādējādi, laika sarežģītība ir atkarīga no realizācijas un var svārstīties no O(m * n) līdz O(m + n).