10 개의 요소가 있고 빈 트리부터 시작하면 big-O 표기법으로 10 개의 요소를 Red Black에 삽입하는 복잡성은 무엇입니까?빈 트리부터 Big-O 표기법으로 Red Black Tree에 삽입하는 과정의 복잡성은 무엇입니까?
요소를 삽입 할 때마다 요소의 적절한 위치를 검색하고 조상 노드와 자식 노드 사이에서 일련의 회전을 수행해야하므로 O (log 10) 이상이 될 것입니다. 그래서 N 요소가 있고 레드 블랙 트리에 N 번 삽입하면 O (n log n)가되지 않습니까?
도움 주셔서 감사합니다.
단일 요소를 RB 트리에 삽입하는 시간 복잡도는 O(log n)입니다. 여기서 n은 트리의 현재 크기입니다.
n 요소를 빈 RB 트리에 삽입하는 시간 복잡성은 따라서 O(n log n)입니다.
10 요소를 빈 RB 트리에 삽입하는 시간 복잡도는 일정하거나 O(1)입니다. 트리가 공백으로 시작하고 삽입되는 요소의 수가 고정되어 있기 때문에 여기에는 가변 요소가 없습니다.
O (10)은 O (1) 또는 O (128291)와 똑같기 때문에 상수 (1 제외)와 함께 big-O를 사용하지 마십시오. 따라서 규칙 상 항상 O (1)을 사용합니다!
그럼 초기에 비어있는 RB 트리에 K 항목을 삽입하는 큰 O가 무엇인지 살펴 보겠습니다. 첫 번째 삽입은 일정한 시간이므로 O (1); X + 1이 O (log (X)) 인 X 항목이있을 때 삽입하면 (각 단계를 회전해야하더라도 로그 (X)에 비례하여 최악의 경우이므로 O (log), "layers"또는 "levels"의 수는 X와 대수적으로 만 증가하기 때문에 - K 레벨에 대한 RB 트리는 K 번째 힘에 2만큼 증가하는 노드를 가지고 있기 때문에).
따라서 X의 log (X) 합계를 2에서 N (더하기 costant)으로, N의 계승 로그와 같아야합니다. Stirling's approx 일 때, N log (N) - N, big-O 용어로 다시 N log (N)로 내려갑니다.
@ Justice와 @Alex는 실제로 N이 무한대로 변하는 것처럼 제한 동작 (예 : 실행 시간, 비교 횟수 등)에 대해 말하기 때문에 O(f(N)) 복잡성 측정 값을 얻고 있습니다.
N을 특정 값으로 대체하면 O이라는 용어는 더 이상 의미가 없다고 말합니다.
또 다른 요지가 있습니다. N이 작을 때 어떤 일이 발생하는지 알려주는 표기법을 O(...) 표기법으로 사용할 수 없습니다. 정의에 따르면 "big O"표기법은 그 경우에 어떤 일이 일어나는지에 대해 알려주지 않습니다.
이것은 단지 pedantry가 아닙니다. 예를 들어, 비용 함수 F(N) = 1,000,000 * N + N**2은 O(N**2)이지만 첫 번째 용어는 1,000보다 작은 N 값을 지배합니다. 이 경우 예상치로 O(N**2) 측정 값을 사용하려고하면 완전히 잘못된 대답을 얻게됩니다.
감사합니다. 정말 잘 설명했습니다. – John
@ 존, 그래서 당신이 그것을 좋아하지 않는 이유는 그것을 받아 들일 수 없습니다 (질문의 왼쪽 상단에 큰 "upvotes"숫자 아래에 체크 표시를 사용하십시오) - 그것은 기본적인 에티켓이므로 SO 평판 사다리에서 시작할 수 있습니다 (그렇습니다, 당신은 받아들이기에 의하여 rep를 얻는다! -). –
@AlexMartelli X 입력 항목이있을 때 삽입하는 것은 'O (X)'대신 'O (logX)'입니다. 좋은 대답 btw, +1. –