Большая эффективность для нескольких переменных

Question

Я пытаюсь оценить эффективность функции, в которой вход представляет собой массив строк.Алгоритм всегда перебирает все элементы в этом массиве.Строки, содержащиеся в этом массиве, имеют переменную длину.В этом начальном цикле for функция замены символов вызывается для каждой строки.Я полагаю, что функция замены сама по себе была бы O (n), где n - длина строки.

Так что я запутался, как оценить здесь большую эффективностьЕсли n - размер массива, я знаю, что он будет по крайней мере O (n).Но с переменной длиной строки, как бы вы оценили общую эффективность с заменой строки?Вы бы сказали, что n - это размер массива, и используете другие переменные для представления разных размеров каждой строки?

Answer 1

Лично я бы выразил эффективность через размер входных данных (в отличие от длины массива).Таким образом, если ввод t байтов, время выполнения будет O(t).И t здесь также общая длина всех строк.

Answer 2

Я вижу два способа сказать это (из многих возможных).

Первый - сказать, что это O(N), где N - общее количество символов.

Другое, что вы можете сказать, это O(N*M), где N - это количество строк, а M - это среднее количество символов в строке.Обратите внимание, что это на самом деле так же, как мой ответ выше.Вы можете сказать M = k/N, поэтому вы получите O(N*k/N) или O(k), где k - общее количество символов во всех строках.