반복자에 대한 상각 된 복잡성

균형 잡힌 트리 (예 : AVL 트리의 상각 된 복잡도가 O (1 + log (N/M)))에 대해 Java의 반복 함수를 구현해야하며 이것이 무엇을 의미하는지 확실하지 않습니까? 모든 링크 나 설명은 매우 도움이 될 것입니다. 고마워요반복자에 대한 상각 된 복잡성

출처

2013-03-24 user1950055

N은 무엇입니까? M이란 무엇입니까? 우리는 이러한 상수가 당신을 도울 수 있도록 설명해야합니다. – templatetypedef

죄송합니다, N은 내 트리의 노드 수, 즉 값이고 M은 내가 오름차순으로 방문한 노드 수입니다. – user1950055

(O (1 + log n)은 O (log n)과 같습니다.) –

반복기의 next() 메서드를 연속해서 호출 할 때마다 해당 메서드 호출의 복잡성이 줄어 듭니다. N 개의 노드가있는 트리의 경우 첫 번째 호출은 O (log (N))의 복잡성을 가져야하며 다음 호출은 O (log (N/2)) 등이 있어야합니다. 복잡성을 이해하기 위해서는 몇 가지 배경 수학과 컴퓨터 과학. 짧고 모호한 설명은 here입니다. 이 주제에 대해 더 깊이 이해하려면 Corman의 글에서 시작해야합니다. Introduction to algorithms

출처

2013-03-24 21:37:17 iGili

반복자에 대한 상각 된 복잡성

답변

관련 문제