알고리즘의 복잡도 분석을 생각하고 있는데,이 예가 나온 것입니다. 여러 의사가있는 의료 센터가 있습니다. 각 의사는 일주일에 1 시간의 시간대에 방문 할 수 있습니다. 이제 우리는 의사 집단을 가지고 있다고 가정하고 의사는 일정한 방문 일정을 소장하고 있다고 가정하면 의사와 함께 특정 슬롯이 무료인지 찾기를 원할 경우이를 수행 할 수있는 매우 기본적인 알고리즘을 작성할 수 있습니다.알고리즘 복잡도 분석에서 큰 상한선을 고려하십시오.
for (Doctor doc: doctors) {
for (Visit visit: doc.visits) {
if (visit.hour == hour && visit.day == day) {
return false;
}
if (visit.day > day) {
break;
}
}
}
return true;
이 문제를 해결하는 데 가장 효율적인 방법이 아니라는 것을 알고 있지만, 시간 복잡성에 대해 궁금합니다. 처음에는 O (n^2)의 시간 복잡성에 대해 생각했습니다. 의사와 방문수가 늘어날 수 있고 코드에 두 개의 중첩 루프가 있고 내부 루프에 두 개의 일정 시간 작업이 포함되어 있기 때문입니다.
그러나 의사의 수에는 센터의 국가에 거주하는 사람들의 수인 상한선이 있다고 생각했습니다. (외국 의사조차도 상한선, 세계 인구 ~ 7.5 억); 그래서 시간 복잡성은 내부 루프가 단지 일정한 횟수만큼 실행되기 때문에 선형 O (n)으로 낮아지는 것으로 보인다. Big-O 용어 : O (C * N) = O (n) 여기서 C는 상한 상한입니다.
나는이 소프트웨어가 1 세기 이상 동안 의료 센터를 운영하지 않을 것이라고 생각했다. 왜냐하면 나는 그 기간에 의료기관이 다시 쓰여질 것이라고 확신하기 때문이다. 그래서 소프트웨어는 2117 년까지만 방문을 허용 할 것이며, 이는 연간 230 근무일, 하루 8 슬롯, 184k 슬롯을 다시 상한으로 가정합니다. 이 소프트웨어가 1 세기 이상 지속될 수 있다고 생각한다면, 상한선은 태양의 예상 수명 (약 50 억년)이되고 그 이후에 지구상의 생명체는 사라질 것입니다. 상한은 높지만 상한은 여전히 있습니다. 따라서 시간 복잡성은 O (C1 * C2) = O (1)이므로 C1이 의사 상한이고 C2가 방문 상한이므로 O (1)로 보입니다.
이 논리가 정확합니까? 일반적으로 알고리즘의 복잡도를 분석하는 동안 큰 수를 상수로 가정하면 정확합니까?
"n이 어떤 상수보다 결코 클 수 없다고 가정하면 f (n)의 복잡성은 무엇입니까?"는 의미있는 질문이 아닙니다. 복잡성은 필연적으로 큰 임의의 n에 대해 f (n)을 고려해야합니다. –
인수를 사용하면 배열의 quicksort가 O (1)라고 주장 할 수 있습니다. 세계에서 가장 큰 컴퓨터가 가장 큰 배열 quicksort의 크기를 제한하는 64TB RAM을 보유하고 있기 때문입니다. –
@ 폴 한킨 : 그게 정확히 내가 생각한 것입니다. 그렇다면 왜 컴퓨터 구조가 본질적으로 유한 한 (그리고 상한선을 가짐) 경우 점근 적 복잡성에 대해 이야기할까요? 내가 뭘 놓치고 있니? –