계산 복잡성 운동

Question

AHO, Hopcroft & Ullman의 "데이터 구조 및 알고리즘"을 읽고 있으며 운동 1.12 B :

이 파스칼 절차의 계산 복잡성 (큰 O 표기법으로 표현 됨)은 무엇입니까?

procedure mysterious( n: integer );
    var
        i, j, k: integer;
    begin
        for i := 1 to n - 1 do
             for j := i + 1 to n do
                 for k := 1 to j do
                    {mysterious statement of O(1)}
    end

저를 좀 도와 주실 수 있나요?

감사!

Answer 1

켜졌 어³). BIG-O는 실행 시간 (또는 메모리 또는 기타)이 작업 크기에 비례하는 방법을 보여줍니다 (비례 계수는 생략 됨).

이 경우 내부 진술은 시간에 비례하여 실행됩니다 (n³). 나는 1에서 (n-1)을 실행하므로 외부 사이클 내부의 모든 것이 실행됩니다 (N-1) 시간. j는 평균적으로 (n/2)에서 (n)에서 실행되므로 내부의 모든 것이 실행됩니다 (n -1)* (n/2) 시간. K는 평균 1에서 (3/4* n)로 실행됩니다. 이것은 내부 진술의 (n-1)* (n/2)* (3/4* n-1) 실행이 발생합니다. 이것은 O (n³).