Сложность времени для поиска списка списков?

Question

Предположим, я сохраняю матрицу в виде списка списков, где первый список представляет строки, а каждый элемент в этом списке представляет собой список, представляющий значения в этой строке. Какова будет сложность времени для поиска элемента?

Если я не ошибаюсь, средняя сложность времени нахождения элемента в списке с помощью линейного поиска равна O (n), означает ли это, что средняя сложность времени для списка списков равна O (n ² )

Answer 1

Если n означает ширину и высоту квадратной матрицы, то линейный поиск в матрице займет O (n ² ) времени. В более общем смысле, линейный поиск в прямоугольной матрице angular m × n займет O (mn) времени. И то, и другое объясняется тем, что это количество записей в матрице, и линейный поиск будет выполнять O (1) работу на каждую запись.

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

Обратите внимание, что вышеизложенное предполагает, что проверка для цели поиска занимает O (1) времени (например, сравнение примитивных целых чисел). Если это неверно, то вы должны умножить вышеприведенное на временную сложность теста на равенство; например, если по какой-то причине у вас есть матрица m × n строк длиной c, то время выполнения будет равно O (mn c).

Answer 2

Ну, у вас будет два индекса. Таким образом, сложность равна двум списку, но умножается на два. Тем не менее, если вы хотите смоделировать матрицу, вы можете рассмотреть возможность использования массива массивов (не путать с неровным массивом), потому что в нормальных условиях матрица имеет фиксированный размер (List<T> является оберткой около T[], чтобы разрешить добавление и удаление элементов).