전체 알고리즘의 시간 복잡도는 얼마입니까?

Question

나는 점근 표기법에 익숙하지 않고 여기에 알고리즘이있다. 시간 복잡성에 대한 최악의 경우 긴밀한 유대는 무엇이며 그 이유는 무엇입니까?

F(A,B) { //A and B are positive 
    while A>0 
    print(A mod B) 
    A=A div B 
} 

Answer 1

이의 시간 복잡도 :

F(A,B) { //A and B are positive 
    while A>0 
    A=A/B 
} 

루프 실행 횟수와 동일,의는 l 및 B를 만들기 위해 분할하는 몇 배에 해당하는 것을 부르 자 "A> 0"거짓. O (m) 단계에있는 긴 나눗셈을 수행 크 누스의 책 "컴퓨터 프로그래밍의 예술"(2 권)의 4.3.1에서

알고리즘 D :이 question에서

, 우리는 알고 m은 A의 자릿수이므로 상한이 있습니다.

따라서, 시간 복잡도는 * O (패 *의 m) * 지금

이 : IO가 일정하다고 가정

print(A mod B) 

(즉, 실시간으로 올바르지 않은 과정의 일이다 WOLRD)는, 당신은 모듈 자체의 복잡성, this에서, 우리가 알고해야합니다

O는 (로그 B 로그)를

이고 l 번 실행됩니다.

은 그 결과, 우리는이 :

O

Answer 2

그것은 아주 좋은 질문이 아니다 (리터 * (m +)는 로그 B 로그). 첫째, B가 일치하면 알고리즘이 완료되지 않습니다. 아마도 B는 2 이상이어야합니다. 그래서 우리는 O (log A) 단계를 가지고 있습니다. 그러나 문제는 그 부서가 그 자체가 "운영"인지 여부입니다. A와 B가 제한이 없다면 본질적으로 대수이어야한다. 하지만 일반적으로 코드는 32 비트 또는 64 비트로 모든 디비전을 구현하는 프로세서에서 실행되며 범위를 벗어나는 수를 나눌 수 없습니다. 그래서 일반적으로 우리는 부서가 "운영"이라고 말합니다.

우리가 나누기가 logarithimic이고 B가 작다면 우리는 O (log A)^2입니다.