정렬 된 링크 된 목록의 실행 시간

요소를 찾고, 요소를 삽입하고, 정렬 된 연결된 목록에서 요소를 제거하는 데 필요한 런타임은 무엇입니까?정렬 된 링크 된 목록의 실행 시간

나는 당신이 관계없이 각 링크를 통과해야하기 때문에 그들은 모두 O (n)이라고 생각합니다. 내가 맞습니까?

2016-11-18 Hello World

여기를 확인 http://bigocheatsheet.com/ – duncan

@duncan 정렬 된 연결된 목록이 없습니다. –

특정 요소를 찾으려면 삽입 및 삭제가 필요합니다. 이것은 그들이 검색과 같은 일을한다는 것을 의미하므로 둘 다 O (n)이됩니다. – duncan

네가 맞습니다. 노드의 순서를 알았는지 여부에 관계없이 모든 노드에 실제로 액세스하는 유일한 방법은 전에 노드를 통과하는 것입니다. 이는 N 개의 노드에 대해 N 개의 노드를 거쳐야 O (N)의 연산을 수행해야 함을 의미합니다.

출처

2016-11-18 21:47:09 Jay

N/2 노드 만 통과하면됩니다. 따라서 정렬 된 링크 된 목록은 동일한 복잡성 등급에 속하지만 아직 두 배의 요소가 있습니다. – bipll

이것은 사실이 아닙니다. 노드 1 개를 이동할 때마다 노드 2 개를 제거 할 때만 O (N/2) 또는 시간 복잡도를 얻습니다. 이것은 여기에 해당하지 않습니다. 목록을 이동할 때마다 노드 하나만 제거합니다. 고려해야 할 최악의 시나리오를 가정하면 시간 복잡도는 O (N)입니다. O (N)은 항상 평균적인 경우는 아니며, 문제의 알고리즘이 O (x)보다 더 오래 걸리지 않을 것이라고 자신있게 말하고 싶다는 것을 기억하십시오! – Jay

정렬 된 링크 된 목록의 실행 시간

답변

관련 문제