У нас есть два списка длин L1 и L2. Мы перешли оба списка один за другим. Какова будет временная сложность общей работы?Это O (L1 + L2) или O (max (L1, L2))?
Это O (L1 + L2) или O (max (L1, L2))?
В чем разница между этими двумя?
Первый вариант O (L1 + L2) является подходящим. Например, в алгоритмах графа, которые используют V для числа вершин, а E для числа ребер, многие операции выражаются через O (V + E), такие как первый поиск глубины в графе. Конечно, в этом случае E может варьироваться от O (V) до O (V^2). Если L1 и L2 фиксированы относительно друг друга, то O (max (L1, L2)) = O (L1) или O (L2) может быть более подходящим.
Между ними нет никакой разницы. Без ограничения общности предположим, что L1 = O (L2); если это не так, то L2 = O (L1), и вы можете просто поменять символы.
O (L1 + L2) = O (2 * L2) = O (L2). Аналогично, O (max (L1, L2)) = O (L2). Таким образом, в обоих случаях сложность O (L2).
@ waldol1: либо L1 = O (L2), либо L2 = O (L1), так как O обозначает асимптотическую верхнюю границу только. –
Это может быть правдой, но мы не можем считать симметрией L1 и L2. Как я уже сказал в своем ответе, при перемещении двух списков переменной длины, длины которых могут быть не одного и того же порядка, то обход обоих приводит к O (L1 + L2). Или в случае, когда известны отношения L1 и L2, тогда достаточно одного O (L1) или O (L2). – waldol1
Я бы также подумал, что это более подходящий ответ, поскольку мы не должны предполагать какую-либо связь между L1 и L2 – sethi