이진 검색의 최상의, 평균 및 최악의 경우의 시간 복잡도는 입니다. 가장 좋음 O (1); 평균 O (log n); 최악의 O (log n); 배열 구현의 경우. 마찬가지로, 삽입 정렬의 최상의, 평균 및 최악의 시간 복잡도는 다음과 같습니다. Best O (n); 평균 O (n^2); 최악의 O (n^2); 배열 구현의 경우.최악의 시간 복잡도 목록
그러나 어떻게하면 이진 검색과 단일 연결 목록의 삽입 정렬과 같은 복잡성을 해결할 수 있을까요? 이중 연결된 목록; 및 순환 링크 목록 구현?
간략한 대답은 알고리즘에 의해 수행 된 컴퓨터 단계를 살펴 보는 것입니다. 알고리즘 증명, BigO, Omega 및 Theta 표기법을 살펴볼 수 있습니다. 알고리즘마다 다른 최악의 시나리오와 최상의 시나리오가 있습니다. 주어진 입력이 n 인 함수 F (n)가 주어집니다. 그것은 G (n) 컴퓨터 단계를 가지고 있습니다. G (n) = 5x^2 + 3x + 1이라고하자. 대부분의 사람들은 대개 Big-O를 본다. Big (O)의 경우 모든 계수를 버리고 선도 기간 만 가져옵니다. Big-O는 x^2가 될 것입니다.
링크 된 목록 (하나의 링크도 아니고 다른 것도 아닌)으로 이진 검색을 구현할 수 없습니다. 모든 인덱스에 대한 O (1) 액세스가 필요합니다. 배열은 간단하지만 목록은 불가능합니다. 요소 n/2에서 n/4으로 전달하는 방법을 생각해 봅시다. 예를 들어 가운데 또는 시작 부분의 모든 요소를 통과하지 않아도됩니다.
삽입 정렬은 연결된 목록에서 문제가되지 않는 요소를 연속적으로 탐색하므로 동일한 복잡성을 유지합니다. O (N^2)는 각 요소에 대해 처음부터 전체 목록을 걸어야하는 경우에도 마찬가지입니다 (단 하나의 연결된 목록의 경우). 정렬. 그러나 알고리즘을 수정해야합니다. 알고리즘을 수정해야합니다. 이는 매우 기본적인 교훈을 보여줍니다. 특정 알고리즘이 데이터 구조를 지정하고 다른 데이터 구조를 사용하면 일반적으로 알고리즘이 변경되고 경우에 따라 복잡성이 필요합니다.
2 진 검색을 사용할 수 있는지 여부는 항목을 임의로 액세스 할 수 있는지 여부에 따라 다릅니다 (색인별로 항목에 액세스). 목록에서 항목에 액세스 할 수 없습니다 (단일 링크 목록; 이중 연결된 목록; 및 순환 링크 된 목록)을 색인별로 구현하므로 목록에서 이진 검색을 구현할 수 없습니다. 그러나 대신 Skip List을 사용할 수 있습니다. 건너 뛰기 목록에서 O (l) (가장 좋은 경우) O (lnN) (평균 및 최악) 검색을 얻을 수 있습니다 ..
삽입 정렬에서 색인으로 액세스 할 필요가 없으므로 배열간에 차이가 없습니다 삽입 정렬을위한 목록 일반적으로 현재 항목을 삽입하려면 이전 항목에 액세스해야하지만 반대 순서로 항목을 정렬하고 처음부터 위치 (예 : 목록의 머리)를 찾고에서 목록을 역순으로 정렬 할 수도 있습니다 . 마지막으로 그것은 시간의 복잡성을 변경하지 않습니다
BinarySearch을 :.?. 이 요소에 랜덤 액세스가 필요합니다, 당신이 좋아하는 목록에 얻을 수 NO (당신이 배열로 변환하기 위해 여분의 공간을 사용할 수 있지만, 하지만 그것은 연결된 목록을 사용해야한다는 사실을 능가합니다. LY)
삽입 종류 : 당신이 얻을 특정 인덱스 전에 요소에 액세스 할 필요가
, 확실히 당신은 (1) 단일 연결리스트에 대한 O에서 그것을 할 수 없습니다.
각 요소의 처음부터 목록을 탐색 할 수는 있지만 시간 복잡성이 매우 높습니다.
이중 연결 목록에서 O (1) 시간에 이전 요소에 액세스 할 수 있으므로 쉽게 삽입 정렬을 적용 할 수 있습니다.
위의 토론에서 순환 목록에 대해서도 쉽게 생각할 수 있습니다.
희망이 도움이됩니다.
가장 좋은 방법은 종이에 목록을 작성하고 배열에 대해 알고있는 알고리즘을 적용하는 방법을 알고 있다면 분명히 차이점을 알 수 있습니다. :) –