복잡도와 Big-O

크기를 조정할 필요가없는 사용되지 않은 공간이 충분하다고 가정 할 때 다음 두 알고리즘의 최악의 시간 복잡도는 무엇입니까? 필자의 초기 추측은 index [0]에 새로운 요소를 추가하기 위해 모든 요소를 이동해야하기 때문에 A가 느리게 실행된다는 것입니다. 나는 B가 최악의 경우 O (N^2)라고 생각하지만 확실하지 않습니다.복잡도와 Big-O

for (int i = 0; i < N; i++) 
     items.add(0, new Integer(i));

및 B.

for (int i = 0; i < N; i++) 
     items.add(new Integer(i));

출처

2013-02-13 user1874239

정말 항목을 저장하는 데 사용되는 기초 데이터 구조에 의존한다. 연결된 목록을 사용하는 경우, A와 같은 삽입은 일정 시간 (예 : O (1))을 사용하는 반면 배열을 사용하면 O (n)가됩니다. 새로운 항목. 따라서 루프는 링크 된 목록이 사용되면 복잡성 O (n)을, 배열이 사용되면 O (n^2)를 갖습니다.

B의 경우 추가 기능을 구현하는 방법이 명확하지 않으므로 복잡성에 대해 언급 할 수 없습니다. 연결된 목록, 배열 또는 균형 트리를 사용하면 복잡성이 달라집니다.

출처

2013-02-13 05:41:50

items는 ArrayList 입니다. 그러나 루프에 n 번 (n-1)/2 => n^2 항목을 n 번 시프트해야하기 때문에 A (N^2 또는 N^3)이 아닌 이유는 무엇입니까? – user1874239

모든 삽입은 O (1) 또는 O (N)을 취하기 때문에 A는 실제로 O (N 또는 N^2)입니다. 나는 그것을 분명히 말해야했다. n^2 항목의 의미는 무엇입니까? 루프 A에 따르면 N 삽입 만하므로 최대 N 개의 항목을 가질 수 있습니다. –

그러나 A를위한 루프의 끝에서 한번 끝까지 끝내면 목록 앞에 새 번호를 추가 할 때마다 n (n-1)/2 숫자를 이동해야합니다. arrayList를 사용하여) B와는 반대로 어디서 끝까지 추가 하시겠습니까? – user1874239

복잡도와 Big-O

답변

관련 문제