시간 복잡도 분석

Question

죄송합니다. 여기에 긴 문맥의 글을 쓸 시간이 없습니다. 이것은 제가 지금하고있는 실습 시험에서 얻은 질문이며 제 모든 대학교 자원은 오프라인입니다 (위대한 Uni, 저는 알고 있습니다). 나는 이것을 시작하는 방법을 완전히 혼란스럽게 생각한다. 누군가 그것을 통해 나를 걸을 수 있을까요? 나는 수학에서 가장 위대하지 않다. 감분 방법에 대한 최악의 경우의 시간 성능 일정하다고 가정

public static int triple(int x) { 
    if (x == 0) return 0; 
    else return add(3, triple(decrement(x))); 
} 

하고 추가 방법은 두번째 파라미터 선 (ADD위한 즉, 시간 (있음 :

는 다음 순환 방법을 고려 x, y) 은 b 및 a에 대해 by+a으로 표현할 수 있으며 인 경우 은 x에 대한 트리플 메서드의 최악의 시간 성능을 나타냅니다. 이 메서드의 복잡성을 계산하려면 첫 번째 여러 메서드 인스턴스 (문제 크기)에 대한 반복 관계를 결정한 다음 표현식 을 일반화하여 nth case의 닫힌 폼 수식을 만듭니다. 당신의 일을 보여주십시오.

Answer 1

x 값을 트리플 메소드가 실행되는 횟수에 매핑하는 테이블을 구성합니다. 그런 다음 둘 사이의 관계를 형성하십시오.

x | executions |    Executions 
------------------------------------- 
0 | T(0)      | 0 A(0) 
1 | T(1) + A(3,1) + T(0)  | 3 A(1) 
2 | T(2) + + A(3,1) + T(1) | 6 A(2) 
3 | T(3) + A(3,1)   | 9 A(3) 

    Time Complexity for T= T(n)+T(n-1)+...+T(n-n) 
    Number of add calls is linear O(n) 

    nth term for number of executions 
    Un = 3+(n-1)d 
     = 3+(n-1)3 

    the sum of the an arithmetic series making it O(n^2) 

Answer 2

먼저 주어진 x에 대해 트리플이 반복적으로 호출되는 빈도를 계산합니다. 위에 제안 된 것과 같은 테이블을 만드십시오. 이것은 당신에게 일반화 된 용어의 일부를 줄 것입니다.

둘째, 트리플을 실행할 때마다 최악의 시간 복잡도는 얼마입니까? 힌트, add() 함수에 의해 결정됩니다.

그런 다음 일반화하십시오.

Answer 3

특정 x에 대해 triple은 0, 1, 2, ... x로 반복적으로 호출됩니다. 재귀 호출 i에서 이러한 인수를 호출 해 봅시다. 인수가 i 일 때 add의 두 번째 인수는 3(i-1)입니다. 즉, add 호출의 비용은 i에서 선형입니다. 따라서 각각의 재귀 호출은 triple에 대한 인수에서 선형입니다. x과 같은 호출이 있으므로 산술 시리즈 (0 + 3 + 6 + ...)의 합계가 있고 O (n) 시간 복잡도입니다.

당신이 코드를 재생할 수 있습니다 :

public class Test 
{ 
    static int time; 
    public static int triple(int x) { 
    if (x == 0) return 0; 
    else return add(3, triple(decrement(x))); 
    } 
    private static int add(int i, int j) { 
    System.out.println("Spending " + j); 
    time += j; 
    return i + j; 
    } 
    private static int decrement(int x) { time++; return x-1; } 
    public static void main(String[] args) { 
    for (int i = 1; i < 100; i+=10) { 
     time = 0; 
     System.out.format("triple(%d)=%d; time=%d\n", i, triple(i), time); 
    } 
    } 
} 

Answer 4

내가 (그리고 모든 좋은 사람들이 나를 가야에 대한 답변을 게시 감사)을 유도 결국 방법은 요헨의 조언을하고을 해결하는 것이었다 좋아 빠른 복잡성 맵, 모든 것을 훨씬 간단하게 만들었습니다.

먼저 add가 O (n) 시간임을 명시하는 질문에 유의하십시오.

다음, 기본 "트리플"호출 계층 구조 :

n | Time complexity: 
------------------------------------------ 
1 | T(1) + (T(0) = 1 ) 
2 | T(2) + (T(1) = ...) 
3 | T(3) + (T(2) = ...) 

분명히 패턴이 등장하고있다 ...

n | Time complexity 
------------------------------------------- 
n | T(n) + T(n - 1) 

는 그래서 T는 트리플 호출에 대 한 시간 복잡도 여기서 T (N)의 시간 복잡도가 n * T 것 같습니다. 호출 성장의 원천이 add에서하고 add의 시간 복잡도는 시간 복잡도는 n * n 또는 O(n^2)

고마워된다, O(n) 것을 감안할 때, 내가 잘못된 용어 또는 무언가를 사용한 경우 알려주세요.

편집 : 일부 추가는 꺼져 있지만 여전히 동일한 BigO 표기법입니다.