Какова шкала временной сложности этого алгоритма?
У меня есть список списка разной длины, и мой алгоритм работает с каждым элементом в подсписках.
Какой должна быть моя временная сложность?
Я не знаю, можно ли писать O(n * m), так как n длина родительского списка, а m — средняя длина t E подсписков или, может быть, O (n), поскольку n - это общее количество элементов.
Пожалуйста, объясните, что означают символы (например, n — это длина родительского списка).
Ответы 3
Если у вас есть n подсписков с m элементами в каждом, n*m представляет общее количество обрабатываемых элементов, следовательно, он имеет сложность O(n*m).
Если ваши подсписки имеют неравное количество элементов, можно обобщить их как O(N), где N — общее количество элементов в массиве.
Вы можете определить свои переменные, поэтому совершенно нормально сказать «O (n), где n - размер ввода».
Ваш случай похож на «разреженные» матричные методы: разреженные матрицы имеют четко определенную ширину и высоту, а также общий размер (ненулевых элементов). В описании производительности алгоритма могут использоваться все три параметра по мере необходимости.
В конечном итоге речь должна идти о том, что удобно для описания алгоритма.
Вы выполняете операцию всего N раз. Поэтому, если ваш алгоритм не обращается к некоторым из этих других элементов внутри него, это делает его операцией O (N). Акт перехода от одного подсписка к другому, даже если он занимает значительное время, является операцией O(m). Но так как m меньше N, вы можете игнорировать его, потому что, когда N становится очень большим, оно превосходит время O(m). Действительно, вся цель анализа «Порядка» состоит в том, чтобы продемонстрировать реакцию алгоритма в экстремальных условиях.