BigO вектора с использованием итератора

Question

Я сделал несколько исследований, но я не нашел хорошую статью.
Я добавляю мультипликатор Vectors одному Vector, после чего я его печати:

Iterator it =vector.iterator(); 
    while(it.hasNext()){ 
     System.out.println(it.next()); 
    } 

Как определить обозначение Big-O для этой функции?
Например, если выход был:

[Что-то, что-то, что-то, что-то]
[Что-то, Что-то, что-то, что-то, что-то]
[Что-то, Что-то, что-то, что-то, что-то , то]
[Что-то, что-то, что-то, что-то, что-то, что-то, что-то ]
[Что-то, что-то, что-то, что-то, что-то , что-то, что-то, что-то]

И что я не понимаю каждую строку - это вектор, для основного вектора нам нужен цикл, но для векторов внутри него нам не нужен цикл, почему?

Answer 1

При вызове toString на коллекции (как Vector), вы получите список, разделенный запятыми, заключенный в квадратные скобки, в toString каждого элемента в этой коллекции.

Итак, что ваш код делает, вызывая toString на каждом Vector в главном Vector, который в свою очередь вызывает toString на каждом элементе. Таким образом, эффективность O (n), где n - общее количество объектов, на которые вызывается toString.

Answer 2

Предполагая, что вы ВСЕГДА следовать этой «лестнице шаблон»:

Если размер первого вектора 1, и размер последнего вектора K, используя формулы суммирования, то сложность:

K*(K+1)/2 

Теперь, если размер первого вектора к < K, мы имеем:

K(K+1)/2 - (k-1)(k)/2 

Наконец, если мы не имеем «лестницы шаблон», но N векторов размера < K, сложность:

K*N 

Надеюсь, это поможет.