728x90
O(N^2)
처음에 다 넣어놓고
1번job, 2번job넣기 ......
빈자리가 있냐 없냐 알아야 하고, 빈자리 중에 가장 오른쪽 찾아야 한다.
(쭉 다 보고 빈자리 있으면 넣고 아니면 버리고)
특정한 자리에 스케줄이 되면 죽는다.
살아 있는 자리들 중에 얼마 이하인 것중에 제일 큰 것 찾기
AVL Tree, Red-Black Tree (밸런스 트리)
바이너리 서치 트리
처음엔 다 살아있으므로 모든 값 BST insert O(n)
x
스케줄되면 죽는다 BST delete O(log n) => 트리에 있는 값들은 아직 안들어간 애들
= O(nlog n)
살아 있는 것 중 일정 값 이하 중에 제일 큰 거 찾기
있는 값이면 그냥 그 값을 찾아서 들어감
ex) 14
10 > 15 < 13 > 14
ex) 12
없는 값이라면 다시 올라가면서 오른쪽으로 내려온거가 답
10 > 15 < 13 < x > 13 > 15 < 10
ex) x
동그라미가 답
부가정보를 쓰면 더 편해짐. 노드의 값은 10이고 아래 서브트리에 1부터 15까지 있다.
10을 찾아라
9를 찾아라 -> 8이 답
바로 답을 알 수 있다. (범위 밖에 있다면 범위 둘 중에 하나가 답이 됨)
이과정
=> O(log n)
그래서 전체는
O(nlog n)