중첩 for 루프에서 Time Complexity를 계산하는 방법은 무엇입니까?

Question

다음 스 니펫의 시간 복잡도는 얼마입니까? 설명해 주시겠습니까?

for(int i=0;i<n;i++){ 
    for(int j=0;j<=i;j++){ 
    //print something 
    } 
} 

Answer 1

외부 루프에는 n 반복이 있습니다.

내부 루프는 외부 루프의 반복마다 i+1 개의 반복 횟수를 갖습니다.

따라서, 내부 루프의 반복의 수는 :

가

1 + 2 + 3 + ... + N

n*(n+1) 
------- 
    2 

같다

이 O(n^2)

인

Answer 2

시간 복잡도를 계산할 때마다 작업을 수행 할 횟수를 찾으십시오.

여러분의 질문에, 당신이하고있는 일이 무엇이든, 무엇인가를 말하면, 당신은 n 길이 동안 실행되는 외부 루프의 횟수만큼 그것을 할 것입니다. 따라서 1 + 2 + 3 + ... n 번 작업을 수행하면 이되고 n * (n + 1)/2 번이됩니다. I = 1, 내부 루프는 I 2 배

실행 들어

따라서, 단순히 (N^2)

Answer 3

1. 는 I = 0의 경우, 내부 루프는 1 시간
2. 실행 O 것 = 2, 내부 루프는 3 회 실행됩니다. ...

n-1. 옵션 I = N-1, 내부 루프가 실행 n 회

그래서, 총 시간 = 1 + 2 + 3 + ... + N

의 N * (N + 1)/2

으로 표현되고 O (n^2)로 표현된다.

Answer 4

시간 복잡도는 n 정사각형 BigO(n^2) 외측 루퍼 들어

1. , 그 내부 루프의 n

2. 원가 1 + 2 + 3,...n-2, n-1, n

그러므로 총 비용 임 O(n^2)

Answer 5

이차 함수 (이차 런타임)

,515,

알고리즘은

차 함수가 내부 루프는 동작의 선형 수 (N) 및 외부 루프를 수행하는 중첩 루프이다 나타나는 주된 이유는 선형을 행하는 경우 이차 것으로 알려져 연산 수 n이므로,이 경우 전체 알고리즘은 연산을 수행합니다.

n은 특정 배열에 포함될 요소의 수입니다.

어레이의 요소 수가 10이면 로직 실행을 완료하는 데 10 * 10 = 100 작업이 필요하다는 의미입니다.

하나의 목록에서 하나의 항목이 발생했는지 확인하는 것이 좋습니다. 목록의 각 요소를 목록을 포함하여 목록의 모든 요소와 비교해야합니다.

이차 함수의 그래프 :

나는 O이 BigO