점근 시간 (Asymptotic Running Time)

Question

for i = 1....n do 
    j=1 
    while j*j<=i do j=j+1 

나는 asymmptotic 실행 시간을 theta (?) 표기법으로 찾아야합니다. 그

3(1) + 5(2) + 7(3) + 9(4).....+....... 

을 발견하고 나는 부분으로 요약을 사용하여 answere을 찾기 위해 노력했다. 그러나 나는 할 수 없었다. ... 누군가 설명하거나 나에게 단서를 줄 수 있습니까? i는 1 내지 n로 변할 때

for i = 1 to n   
do for j = 1 to floor(sqrt(n)) 

이 때문에, 우리는 sqrt(i)의 시그마으로 전체적인 복잡도를 얻을 :로

Answer 1

코드 조각의 전체 복잡도는 재기록 될 수있다. 불행히도 일련의 평방근 합계에 대한 기본 공식이 없기 때문에 통합에 의존해야합니다.

한계가있는 sqrt(i)의 통합은 n sqrt(n) (상수 인수 무시)입니다.

따라서 루프의 전체 시간 복잡도는 n sqrt (n)입니다.

Answer 2

시그마 표기법을 사용하여 체계적으로 진행할 수 :

세타를 얻으려면, 당신은 (명확하지 않다) 난의 낭패 제곱근의 합계의 공식을 찾아야한다.

안전을 위해 빅 오을 선택했습니다.