Сложность времени для итерации по симметричной матрице (или n-мерным массивам) - PullRequest
Новая
       34

Сложность времени для итерации по симметричной матрице (или n-мерным массивам)

0 голосов
/ 16 февраля 2019

Мне интересно узнать сложность времени для итерации по симметричной матрице .

Я знаю, что для стандартных матриц (2-мерных массивов) сложность O (Nˆ2) .Однако для симметричных матриц мы итерируем только по верхней треугольной его части , а не по всем ее элементам.

Это обычный алгоритм для итерации по симметричной матрице: 

for(int i=0; i < symmetricM.length; i++) 
        for(int j=i; j < symmetricM.length; j++ )
            System.out.println("Elem: "+symmetricM[i][j]);

Я хотел бы, если возможно, расширить те же рассуждения для любых симметричных многомерных массивов.

Я не мог рассчитать это сам, но так как многие проблемы решаются с помощью этого подхода, я хотел бы быть доволен им с точки зрения сложности.

Спасибо.

1 Ответ

0 голосов
/ 17 февраля 2019

Давайте посмотрим на количество элементов, которые мы перебираем в симметричном 2-мерном массиве, это n^2/2, так как размер равен n, и есть 2 размеры, поэтому мы возводим в степень 2 и делим на 2чтобы получить только половину элементов.Итак, O(n^2).

Теперь давайте посмотрим, сколько элементов мы перебираем в симметричном трехмерном массиве.Это n^3/6.Вы можете сделать вывод, что таким же образом вы вычисляете объем трехмерного треугольника , так как все числа находятся в этой треугольной области.Даже после того, как мы поделили на 3, временная сложность составляет O(n^3).

Для четырехмерного это будет n^4/(4*3*2), что составляет O(n^4).Но для m измерений это будет n^m/m!, и поскольку измерение является параметром, в настоящее время сложность времени будет O(n^m/m!) в соответствии с этим методом.

Другой метод вычисления заключается в том, что при удаленииПо диагонали этого измерения индексы элементов, которые вы перебираете, совпадают с комбинациями, если у вас нет повторяющихся элементов и все элементы различны.Мы знаем, что количество комбинаций для этого составляет n!/m!(n-m)! или n choose m, так что это также может быть сложностью по времени.

В соответствии с большинством факторных приближений наибольший элемент равен n^nпоэтому при использовании этих приближений и игнорировании относительно небольших факторов сложность времени остается той же, поскольку:
n!/m!(n-m)! ≈ n^n/m!(n-m)^(n-m) > n^n/m!n^(n-m) = n^m/m!.

Таким образом, со временем сложность времени будет O(n^m/m!).

...