감독 된 분류 문제에 대해 임의의 포리스트로 작업하고 있으며 k-means 클러스터링 알고리즘을 사용하여 각 노드에서 데이터를 분리합니다. 알고리즘의 시간 복잡도를 계산하려고합니다. (; K & middot의, I 및의 middot; D N & middot의)하나의 알고리즘의 시간 복잡도가 다른 알고리즘으로 계단식으로 연결됩니까?
O이고 포인트
k, I 및 d는 상수이거나 n이이 세 개에 비해 훨씬 크기 때문에 복잡성은 단지 O (n)라고 가정합니다.
다른 한편, 임의의 포리스트는 divide-and-conquer 접근 방식입니다. 따라서 n 인스턴스의 경우 복잡성은 O (n & middot; logn)입니다. 잘못된.
알고리즘의 복잡성을 얻으려면이 두 가지를 추가하면됩니까?
이 경우 값을 함께 추가하지 마십시오. 당신은 분할 정복 알고리즘이있는 경우, 런타임은
이러한 매개 변수 중 하나를 변경하면 기능의 전체 런타임에 크게 영향을 줄 수 있습니다. 적은 양으로도 호출 당 subproblems의 수를 늘리면 전체 subproblems의 수를 기하 급수적으로 늘리면 전반적인 큰 영향을 미칠 수 있습니다. 비슷하게 레벨 당 수행되는 작업을 증가 시키면 매우 많은 하위 문제가 있기 때문에 런타임이 크게 흔들릴 수 있습니다. 이러한 수량을 기반으로 런타임을 결정하는 방법의 예로서 마스터 정리 (Master Theorem)를 확인하십시오.
당신의 경우 런타임이 O (n log n)이고 레벨 당 O (n) 작업을하는 단계에서 추가된다는 점을 알고있는 Divide-and-conquer 알고리즘으로 시작하고 있습니다. 이 사실을 알기 만하면 런타임이 무엇인지 판단 할 수 없다고 생각합니다. 반면에, 당신이 알고리즘은 재귀 적으로 독립적으로 그 두 가지를 처리
그런 다음 마스터 정리에서 주어진 재발에 대한 해결책이므로 런타임이 O (n log n)라고 결론을 내릴 수 있습니다.
알고리즘의 내부 작동에 대한 자세한 내용이 없어도 확실하게 말할 수는 없습니다.
희망이 도움이됩니다.