시간복잡도가 list에서 insert()는 중간 위치에서


O(n)이나와야잖아 근데 왜 O(1)이 나오는거냐


어디서 코드를 내가 잘못 쓴거지


int main()

{


int timesToLoop = 1000;


for (int n = 100000; n <= 2000000; n += 100000)

{

list<Student> dll;

list<Student>::iterator it;

Student student1("u1000", "solomon", "physics");


for (int a = 0; a < n; a++)

{

Student student("u1000", "solomon", "physics");

dll.push_back(student);


}

it = dll.begin();

advance(it, dll.size() / 2);

auto startTime = std::chrono::high_resolution_clock::now();

for (int i = 0; i < timesToLoop; i++)

{

dll.insert(it, student1);


}

auto midpointTime = std::chrono::high_resolution_clock::now();


long totalTime =

std::chrono::duration_cast<std::chrono::nanoseconds>(midpointTime -

startTime).count();



long averageTime = totalTime / timesToLoop;

cout << n << "\t" << averageTime << endl;

}

}





이렇게 나오던데


100000  2342

200000  1808

300000  2279

400000  1895

500000  2216

600000  4474

700000  2275

800000  1817

900000  2322

1000000 2782