Вопрос:
Возьмем, например, ввод данных от пользователя для одномерного массива размера n, мы знаем, что сложность времени – это O (n).
for(i=0;i<n;i=i+1) { scanf(«%d»,&a[i]); }
Теперь, если массив двумерный, сложность времени равна O (n ^ 2)
for(i=0;i<n;i=i+1) { for(j=0;j<n;j=j+1) { scanf(«%d»,&a[i][j]); } }
Но даже двухмерный массив сохраняется так же, как одномерный массив. Это просто увеличение размера, почему разница?
Лучший ответ:
Разница во временной сложности – это количество элементов, которые вы храните.
Для линейного массива 1D вы сохраняете n элементов линейным способом, и он также сохраняется в линейном режиме. Таким образом, сложность времени O(n)
Для 2D-массива можно предположить, что вы храните m элементов, которые фактически хранятся линейным способом только в памяти. Но с вами работают элементы, разделенные на строки (и столбцы). Например, размер каждой строки и столбца равен n, тогда вы читаете n*n элементов, которые представляют собой всего лишь m элементов (m == n*n). Таким образом, сложность O(m) или O(n^2)
Ответ №1
как если бы у вас было n элементов, это было бы O (n) в любом случае, но если вы измеряете на основе одного из размеров массива, вы не будете n ^ 2, если это не квадратная матрица (Я вижу, что у вас есть)… так лучше думать об этом как O (h * w) или просто 0 (n) в любом случае…