0
정렬 된 복소수 계산이 복잡해 짐을 증명하려고합니다. LinkedList는 O (1)입니다. 최악의 경우는 O (n)이지만 적절한 잠재 기능을 찾기가 어렵다는 것을 알고 있습니다. 누군가가 도울 수 있으면 기뻐할 것입니다.정렬 된 연결 목록의 경계를 상각합니다
감사합니다.
A
답변
0
O (1) amortized는 n 개의 삽입 시퀀스가 최악의 경우 O (n) 시간의 비용을 의미합니다. 요소를 역순으로 삽입하는 것은 O (n * n)을 취하기 때문에이 경우에는 사실이 아닙니다.
당신이 증명하려고하는 진술은 너무 분명히 거짓이므로 "상각 된"이라고 쓰면 뭔가 다른 것을 의미하는 것으로 의심됩니다. 컨텍스트가 무엇이며, 상환 된 복잡성이 의미하는 바는 무엇입니까? – delnan
@delnan은 일종의 avarage입니다. 그리고 상각 된 비용이 O (1)이라는 생각은 위키 백과에서 온 것입니다. –
평균 작업 수에 대한 평균 (평균 매개 변수를 사용한 단일 작업 시간과 반대), 예. Wikipedia가 구체적으로 말하는 곳은 어디입니까? – delnan