0
복합물 함수로 계산 된 복소수의 알고리즘이 있습니까? f가 O (n^2)에 속하고 g가 O (n)에 속한다고 가정 해 봅시다. 복잡성 f (g (n)), 마녀가 O (n^2) 인 알고리즘이 있습니까?복합물 함수로 계산 된 알고리즘 복잡도
A
답변
0
실생활에서이 사례를 결코 만난 적이 없지만 그런 알고리즘을 상상할 수 있습니다. 예를 들어 런타임 중에 다른 알고리즘을 분석하는 알고리즘입니다. 예를 들어 서로 다른 비교 기반 정렬 알고리즘과 수행 된 모든 비교를 저장하고, 소요 시간을 측정하고, 정렬하고, 일부 통계를 수행하는 알고리즘 분석기를 사용할 수 있습니다. 두 번째 알고리즘의 복잡도가 f(n) 인 경우 비교 항목이 입력되고 정렬 알고리즘이 g(n) 인 경우 크기 n의 입력에 대한 정렬 알고리즘 분석을 실행하면 전체 복잡도는 f(g(n))이됩니다.
어쨌든 n은 f(n)과 g(n)에서 똑같은 것은 아니기 때문에 어떤 종류의 트릭입니다. 기본적으로 복잡도와 대략 동일한 크기를 가진 algo1의 출력에 알고리즘 algo2을 실행하면 효과가 있습니다.