알고리즘의 복잡도를 계산하는 방법은 무엇입니까?

Question

현재 알고리즘 과정에 대한 소개를하고 있으며이 문제를 해결하는 데 도움이 필요합니다. 의심스럽고 그렇게 확신 할 수 없기 때문에 위에 보여졌습니다. :) 두 가지 질문이 있습니다.

질문 1 :내 알고리즘에 대한 책에서 알 수 있듯이이 문제의 런타임 복잡성은 f (n) = 3n이라고 생각합니다. 왜? 왜냐하면 while 루프는 n 번 실행되기 때문에 루프의 각 반복마다 3 번의 연산 (1 빼기, 1 곱셈, 1 덧셈)이 이루어지기 때문입니다. 대입 문으로 인해 실제로 f (n) = 5n이되어야합니다. 나는 둘 다 똑같은 복잡성을 가지고 있음을 알고 있지만, 나는 분명히 확실하게하고 싶다.

질문 2 : 알고리즘이 다항식의 값을 찾으면 보여줄 수있는만큼, 특정 다항식의 값을 찾는 예제를 제공하기에 충분합니다. 3n^2 + 2n + 1을 증명하면됩니다. 알고리즘이 작동하거나 그렇게하는 더 좋은 방법이 있습니다.

Answer 1

첫 번째 질문에서 복잡성은 실제로 O (n)입니다.

당신이 물어 보는 것처럼 더 정확하게 결정하기를 원한다면 모든 루프 중에 알고리즘이 일정한 작업량을 필요로 할 것입니다. (나의 복잡한 레슨은 조금 오래되었지만 나는 그리울 필요가 없습니다.))

1. 루프 조건 분석 : 나> = 0
2. 는 x와 y의 곱 계산
3. 은 [I] Y에
4. 스토어 결과에 따라서 추가
5. i - 1을 계산하십시오.
6. 저장 결과에서 내가

여러분의 프로그램도 3 개 여분의 작업을 수행합니다

1. Y = 0
2. I = N
은하지 않고, 내가 0 마지막 시간을 비교 루프 입력

컴퓨터가 y 및 i 등에 메모리를 할당해야한다는 사실을 고려할 수도 있습니다.

두 번째 질문의 경우 수학과 마찬가지로 한 상황에서 작동한다는 것을 증명하는 것만으로는 충분하지 않습니다.

알고리즘을 증명하려면 우선 전제 조건을 입력해야합니다 (입력 할 내용). 그런 다음 프로그램이 while 루프가 시작될 때와 그 끝에서 동일한 상태를 나타내야합니다.예를 들어

: Y = 0 난 = N 동안 (ⅰ> = 0) { // Y = SUM (A [J] + X^J, j는> I) Y는 [I를 = ] + x^i // x * y 대신 x^i 인 것으로 가정합니다. y = Sum (a [j] + x^j, j> i-1) i = i-1 // y = 합계 (a [j] + x^j, j> i) }

프로그램에 대해 필요한 전제 조건을 찾지 못했습니다. 이전에 언급 한 바 있습니다. 다른 비슷한 작품들. 그림과 같이 아이디어는 각 지점에서 프로그램의 상태를 보여 주므로 끝까지 도달 한 상태를 알 수 있습니다.