Какая временная сложность у этого алгоритма?

Question

[KarakulovWebDev]

есть алгоритм для поиска медианты в двух отсортированных массивов

сформулирована она след образом:

Заданы два отсортированных массива и размера и, соответственно, вернется медиана двух отсортированных массивов.nums1nums2mn

Общая сложность времени выполнения должна быть .O(log (m+n))

есть решение на JavaScript

var findMedianSortedArrays = function(nums1, nums2) {
    const sumLength = nums1.length + nums2.length
    const isEven = (sumLength % 2) === 0
    const startMedianIndex = isEven ? (sumLength / 2) -1 : Math.ceil(sumLength / 2) - 1

    for (let i = 0, i1 = 0, i2 = 0; i < sumLength; i++) {
        const n1 = nums1[i1]
        const n2 = nums2[i2]
        let current = 0

        if (n1 <= n2 || typeof n2 !== 'number') {
            i1++
            current = n1
        } else {
            i2++
            current = n2
        }
        if (i === startMedianIndex) {
            if (isEven) {
                let next = 0
                if (typeof nums1[i1] === 'number' && typeof nums2[i2] === 'number') {
                    next = Math.min(nums1[i1], nums2[i2]) 
                } else {
                    next = typeof nums1[i1] === 'number' ? nums1[i1] : nums2[i2] 
                }
                return (current + next) / 2
            } else {
                return current
            }
        }
    }
};

какая сложность у этого алгоритма и почему?

Comments

[res2001]

Сложность О(startMedianIndex), т.е. это O(m+n)
Потому что массивы просматриваются до i == startMedianIndex, а дальше принимается решение какое из значений будет медианное и алгоритм завершается.
Это далеко не O(log(m+n)).

Answer 1

[Mikhail Osher]

Не силен в этой теме, но вот какие мысли.

Есть два списка размером M и N.
Есть 1 цикл до M+N.
Внутри цикла нет вложенных циклов.

O(M+N)

Answer 2

[Dima Polos]

O(n)

Comments

[Dima Polos]

m+n дает число, это все равно что дать массив большей длины, а потому зависимость будет линейная, другое дело если бы внутри цикла был другой цикл, тогда квадратичная или m*n, но конкретно здесь m+n это тоже самое как если дать массив большей длины - просто проход по массиву

Answer 3

[Wataru]

Линейная. O(N+M). Ибо там цикл по i от 0 до startMedianIndex и вся остальная мишура на i вообще никак не влияет. Больше циклов в программе нет. Не понимаю, что тут может быть непонятного.