Quelle est la complexité temporelle de la déclaration d'un tableau 2D?

Question

Quel est le pire scénario de déclaration d'un tableau 2D? Le tableau 2d n'est pas strictement carré. J'ai vu des réponses qui indiquent qu'il est O (n) et j'ai aussi vu des réponses qui indiquent son O (n²).

Dans mon esprit, lors de la déclaration d'un tableau d'objets comme celui-ci:

Object[][] gridArray = new Object[i][j]; 

//The number of elements n = i*j 

La complexité du temps lors de la déclaration du tableau doit être O (n) car elle échelle juste en fonction de façon linéaire sur le nombre d'éléments il y aura être. Est-ce que je manque quelque chose?

Answer 1

Cela dépend de ce que vous voulez dire par n.

Certains peuvent définir n comme i et voir le j dépendu que, par exemple un carré n * n, pour cette définition que vous obtenez O(n^2), O(i * i) ou O(i * j) si j in O(i).

Cependant, vous l'avez défini comme n = i * j. Donc oui, c'est O(n) pour votre définition de n mais cette notation cache O(i * j) ce qui peut être plus approprié. Notez toutefois que cela dépend si votre langue initialise réellement toutes les entrées de tableau lors de la création. Certaines langues ne le font pas!

Je suppose que votre code est Java, cette langue définit en fait chaque entrée à une valeur initiale. Dans votre cas, ce serait null, donc il crée en effet i * j éléments et les définit à null, ce qui donne O(i * j).

Jetez aussi un coup d'œil à Syntax for creating a two-dimensional array, qui explique en détail comment votre code fonctionne.