1a.) 루프가 아래에 있으며 실행 시간을 찾고 싶습니다. 다음은 그러나 2를 위해 내가 할 때마다 j = i,이 루프는 내가 여러 번 실행하기 때문에 그것은 또한 O에서 (n)의 시간을 실행 생각, 쉽게중첩 for 루프의 실행 시간
sum = 0
for (int i =0; i < N; i++){
for(int j = i; j >= 0; j--)
sum ++
루프의 첫 번째는 O (N)에서 실행되는 루프입니다 .
그래서이 편지에는 실행 시간이 O (n^2)입니다.
1b.) 또한, 누군가가 또한 의미가 무엇인지 설명 할 수 있습니까? 문제가 "theta bound"를 요구할 때?
글쎄, 정확한 루프 반복 수를 계산하는 것은 꽤 간단합니다.
N (N + 1)/2와 합하면 알고리즘 복잡도는 O (N 2)가됩니다. 1 + 2 + 3 + 4 + 5 + 6 + 7 +).
나는 theta bounds를 만났다고 말할 수 없다 ... Wikipedia page on big-O notation은 그것을 언급한다. 따라서 은으로 시작한다.
그래서 내부 루프의 반복 횟수는 외부 루프의 반복 횟수입니까? –
@ user373466 : 아니요, 외부 루프는 N 번만 실행 중입니다 ...하지만 추가 작업을하지는 않습니다. –
f(n) = O(g(n)) 큰 경우에만 nc과 같은 f(n) <= c*g(n)이 있습니다. 기본적으로 big-O 표기법은 상한을 제공합니다. 프로그램이 O(n^3), O(n^2011), 심지어 O(n^42142342)까지 실행된다고 말할 수 있습니다. 그러나 이것들은 당신에게별로 도움이되지 않을까요?
쎄타 표기법을 사용하면 타이트한 값인이 더 유용합니다. f(n) = Theta(g(n)) 큰 숫자의 경우에만 nc1, c2과 같은 c1*g(n) <= f(n) <= c2*g(n)과 같은 정수가 존재합니다. 즉 알고리즘이 비례하는 정확한 함수를 알고 있음을 의미합니다.
알고리즘이 1 + 2 + 3 + ... + N 연산입니다 (최대 N(N+1)/2). N^2/4 + N/4 <= N^2/2 + N/2 <= N^2 + N이기 때문에 Theta(N^2)입니다. 따라서 위의 정의에서 c1 및 c2을 1/2 및 2으로 가져올 수 있습니다.
대부분의 경우 사람들은 큰 경계를 표현하기 위해 big-O 표기법을 사용하지만 이는 필수 사항은 아닙니다. 함수의 big-O를 묻는 질문에는 항상 복수 응답이 있지만 theta 경계를 묻는 질문에는 하나의 대답 만 있습니다.
big-O 정의가 불분명합니다. 그것은 상수'c'가'n'에 의존 할 수있는 것처럼 읽습니다. "... N이면 모든 N> N에 대해"N "과"C "가 존재해야합니다 ..." –
@Chris Hopman - 상수라면'n에 의존 할 수 없다는 것이 분명합니다. '변수입니다. 나는 그것을 가능한 한 간단하게 유지하려고 노력했다. – IVlad
그래서 "theta bound를 찾는다"라는 질문에 대한 답은 0.5 (n^2) = (n^2) = <2 (n^2)일까요? n은 0보다 크거나 같습니까? –
쎄타 바운드는 단단한 점근선 경계를 의미하며 실행 시간을 위아래로 제한합니다. 귀하의 예에서 N^2는 실행 시간의 상한과 하한 모두이므로 실행 시간에 세타 바운드입니다. 공식적
더 :
존재 K1 및 K2되도록 :
N^2 * K1 < = N (N + 1)/2 < = N^2 * K2
위한 N> 어떤 값 N0.
ps.이 책은 다른 점근선 범위에 대한 좋은 설명을 제공합니다 : http://www.amazon.com/Introduction-Algorithms-Third-Thomas-Cormen/dp/0262033844/ref=sr_1_1?ie=UTF8&qid=1295777605&sr=8-1
숙제 문제! 교과서를 읽으십시오. – Neo