무언가를 추가 할 수있는 유일한 Big-Oh 동작은 전체 목록을 탐색해야하므로 링크 된 목록은 O (N)이됩니다. 그러나 전반적인 작업 횟수는 N/2 이상이어야합니다. 누군가가 이것이 가능한 방법을 설명해 주시겠습니까? 링크 된 목록의 양 끝에서 건너 뛴다면 전반적인 동작은 여전히 O (N)이됩니다. 내가 뭘 놓치고 있니?이중 링크 목록에 대한 링크를 추가하면 O (N) (int index, element a) 대신 N/2를 수행 할 수 있습니다.
길이 N의 이중 연결 목록에서 임의의 위치에 요소를 삽입하는 것이 왜 항상 최대 O (N/2)를 차지하는지 묻는다면, 이는 항상 별도의 포인터/참조를 유지해야하기 때문일 수 있습니다. 중간 요소 및 총 요소 수의 계수를 사용하면 지정한 위치에 삽입하기 위해 목록의 반을 넘기면됩니다.
예를 들어 E 요소에 대한 포인터가 있고 목록에 7 개의 항목이 있다는 것을 알고 있다면 [B, C, D, E, F, G, H]의 목록이 있다고 가정 해보십시오. insert(0, A)을 호출하여 위치 0에 A을 삽입하면 링크 3 개를 거슬러 올라가면 위치 3에서 위치 0으로 이동합니다. (0 인덱스가 첫 번째임을 기억하면 E @ 3 - >D2->C @ [email protected] 0). 그곳에서 '현재'요소 앞에 A 요소를 삽입 할 수 있습니다 (B).
사람들은 대개 big-O 분석에서 일정한 용어를 사용합니다. O (n/2) 및 O (n)은 n과 동일한 성능 특성을 갖습니다.
주문하는 데 신경 쓰지 않는다면 링크 된 목록에 뭔가를 추가하는 것이 O (1) 일 수 있습니다. 항상 한 쪽 끝에 새 항목을 추가하십시오.
N/2는 목록이 정렬되어 있다는 가정하에 계산되므로 평균적으로 목록의 절반 만 트래버스하여 올바른 삽입 지점을 찾습니다.
항목에 임의로 액세스하려는 경우 실제 답변은 간단합니다. 연결된 목록 이외의 것을 사용하십시오.
나는 이것이 O (N) 일 것이라고 배웠지 만, 아마도 한 번에 O (N/2)로 이동했다면 가르쳐 주었을 것입니다. 알고리즘의 수치 계수는 컴파일러/언어/하드웨어와 같은 요소로 인해 O (N) 알고리즘이 O (N/2)보다 빨리 완료 될 수 있기 때문에 다소 까다로운 사업입니다. – Mikhail