알고리즘의 시간 복잡도 솔루션에 대한 설명이 필요합니다.

Question

소프트웨어 엔지니어링 클래스에 대한 소개는 시간 복잡성에 걸렸으며 특정 알고리즘을 분석하는 방법을 배우는 중입니다. 나는 그들이 어떻게 그들의 해결책에 도달했는지를 알기가 어려워 누군가가 그것을 설명 할 수 있기를 바랐다.

void foo(int N) { 
    int k = 1; 
    while (k < N * N) { 
     k = k * 2; 
    } 
} 

이들 솔루션은이 기능의 큰-O는 점이다 O (logN)는

내가 생각함으로써이 문제를 해결하려 [나는 여기에 로그가 기본이 이해] 얼마나 많은 시간이 것 임의의 값을 N에 할당하여 반복하고 패턴을 찾을 수 없습니다. 어떤 도움이 필요합니까?

Answer 1

k이 매번 2의 인수만큼 증가한다는 사실은 알고리즘을 logN으로 만드는 것입니다. 실제로는 log(N^2)이지만 대수 특성을 사용하면 2log(N)으로 단순화 한 다음 N이 무한으로 가까워 지므로 한도를 으로 가져와 2을 삭제할 수 있습니다.

따라서, 시간 복잡도는 O(logN)입니다.

EDIT : 또한, 볼 수 k1에서 시작 k보다 크거나 N * N 같을 때, 프로그램은 종료된다. log(N^2)을 사용하면 프로그램을 실행할 반복 횟수를 알 수 있습니다. 이렇게하면 log(N^2)의 한도를 취하여 k의 종료 값을 결정할 수 있습니다.

편집 : 예 : N = 10 : N의 제곱은 100입니다. 따라서 k은 100 이상의 2의 제곱 (128)까지 증가합니다.

Answer 2

고등학교 대수학을 사용하십시오. p 반복 후 k의 값은 2^p입니다. (이것을 확인하기 쉽습니다.) k >= N^2 일 때 루프가 실행을 멈 춥니 다. 대체, 루프는

2^p >= N^2 

지금 해결할 때 중지 :

log_2(2^p) >= log(N^2) 
p >= 2 log(N) 

그래서 루프가 2 log(N) 반복 매우 가까이에서 중지됩니다. 이것은 O (log (N))입니다.

피연산자의 크기에 고정 된 제한이있는 경우에만 곱셈이 일정 시간임을 지적하여 교사에게 맡길 수 있습니다. 그러한 한계가 없으면, 문제는 곱셈의 점근 적 행동에도 달려있다.

덧붙여 말하자면, O (log N)는 대수의 모든 기준에서 동일합니다. 기본은 로그의 값을 상수 요소로만 변경하고 big-O는 상수 요소를 무시합니다.