Временная сложность ввода данных

Вопрос:

Есть ли какие-либо затраты на использование 2d-массива в качестве входных данных?

 
for(int i = 0; i < n; i  ) {
   for(int j = 0; j < n; j  ) {
     cin >> a[i][j];
   }
}

Это временная сложность O (n ^ 2) или O(1)?

1. оба цикла выполняются для n итераций, так что это n ^ 2.

2. Временная сложность цикла — это одно, «сложность» фактического ввода — другое. С точки зрения измерения времени сам ввод уменьшит время выполнения кода,

Ответ №1:

Временная сложность зависит от того, как вы ее определяете. В конкурентном программировании есть вероятность, что вам может быть предоставлена готовая 2D-матрица, и вам нужно найти конкретный ответ. Теперь, какой подход вы используете при поиске ответа, определяет вашу временную сложность. Но в этом случае ввод не учитывается при определении временной сложности, поскольку для вашего использования вам нужна 2D-матрица.

Проще говоря, если вам задано n в качестве переменной и вам нужно ввести n * n элементов, сложность равна O (n ^ 2).