Есть ли способ провести эмпирическое время по алгоритму без учета времени, необходимого для итерации по N элементам? - PullRequest
Новая
       16

Есть ли способ провести эмпирическое время по алгоритму без учета времени, необходимого для итерации по N элементам?

0 голосов
/ 18 апреля 2019

Я запускаю временную проверку алгоритма для ArrayList, который я создал, взяв системное время перед добавлением N элементов и время после добавления N элементов.При анализе кода я знаю, что алгоритмы сложности времени O (1).Однако при выполнении этих тестов я получаю времена, которые не представляют O (1).Времена, которые я получаю, приведены ниже.

n = 10000 3,38 мс

n = 100 000 13,43 мс

n = 500 000 53,02 мс

n = 1 000 000 121,2мс

Я предполагаю, что это потому, что я добавляю N элементов и для цикла, который проходит через эти элементы, он тратит дополнительное время, когда N увеличивается.

Есть ли способ отключить время, необходимое для перебора списка из N элементов?

Вот мой алгоритм, чтобы показать, что это определенно O (1). 

public boolean addLast(E obj) {
  if (this.isFull()) {
    return false;
  }
  if (obj == null) {
    System.out.println("Invalid data, ignoring");
    return false;
  }
  int idx;
  if (this.isEmpty()) {
    idx = this.arrRear;
  } else {
    if (this.arrRear + 1 < this.circArr.length) {
      idx = this.arrRear + 1;
    } else {
      idx = 0;
    }
  }

  this.circArr[idx] = obj;
  this.arrRear = idx;
  this.items++;
  this.modsMade++;

  return true;  
}
...