n + 1과 2 ** ceil (log2 (n + 1)) 사이의 차이를 찾기 위해 프로그램을 실행했습니다. 여기서 n은 2의 거듭 제곱입니다.함수에 ceil이있을 때 점근 적 복잡성을 찾는 방법은 무엇입니까? (2^(2^ceil (log2 (n)))) = O (2^n)?
이2^(2^ceil(log2(n))) <= c' * 2^n
따라서
(2^(2^ceil(log2(n)))) != O(2^n)
위의 문이 올 수 있을까요 - O, 정수를 C '하도록이 없다 - 그것은 큰의 정의에서 이렇게 기하 급수적으로
을 증가 계속? 그렇다면 어떻게 증명할 수 있습니까?
모든 상수 c에 대해 2^(2^ceil (log2 (n)))> c * 2^n 인 n이 존재 함을 입증해야합니다. 어떤 정수 k> 1에 대해서 n = 2^k + 1 만 고려해 봅시다; 이것이 우리 모두의 진술을 증명하려고하지 않기 때문에 우리의 권리입니다. 원하는 부등식은 다음과 같이됩니다.
2^(2^ceil(log2(2^k + 1))) >? c * 2^(2^k + 1).
왼편을 단순화합니다.
ceil(log2(2^k + 1)) = k + 1
2^(2^ceil(log2(2^k + 1))) = 2^(2^(k + 1)).
원하는 부등식 (및 n)은 현재 분명이 부등식
2^(2^(k + 1) - 2^k - 1) = 2^(2^k - 1) >? c.
2^k - 1 >? log2(c)
2^k >? log2(c) + 1
k >? log2(log2(c) + 1).
K의 선택에 해당
2^(2^(k + 1)) >? c * 2^(2^k + 1).
이고; 원하는 부등식을 나타 내기 위해 부등식을 거쳐 역으로 작업하므로 함수는 O (2^n)이 아닙니다.
나는'2^k + 1'의 선택의 중요성이 강조되어야한다고 말하고 싶었습니다. 이것은'ceil'을 다루는 가장 좋은 방법입니다. 추가 분석을 위해서는 매우 중요합니다. 나는 당신이'2^(2^log2 (n))'과'2^(2^(log2 (n)))'에 의해 바인드를 금지한다고 생각하여 실수를했다.) +1))'. 'ceil'이 반올림되지 않는 경우를 위해'n'을주의 깊게 선택하고'2^ceil (log2 (n))) = n'을 제거하면'O (2^n)'과 동일합니다. "낙관적 인 경우"에서 항상'2n'이되어'2^f (n)'에 차이가 생깁니다. – luk32
명확성을 위해'ceil'이 올림하는 경우'2^(2n)'과'O (2^n)'<'O (2^(2n))'처럼 행동합니다. 그런데'ceil (log2 (2^k + 1)) = k + 1' 가정이 명확하지 않을 수 있도록 비 정수형'k'에 대해 이것을 증명할 수 있습니까? 나는 당신이 함수에 대한 특정 값을 선택할 수 있다는 점이 흥미 롭다. 그리고 점근 적 행동은 다르다. 내가 눈치 채는 약점이 하나 있습니다. 예를 들어 "* n은 2 *의 힘입니다."라고하는 OP의 제약 조건을 위반하는 것입니다. "2 * 1의 힘"이라고 말하면 일반 분석에는 적합하지만 특정 사건에 대해 많은 것을 바꿀 수 있습니다. – luk32
2^(2^천장을 만들다 (LOG2 (N))) < 2^(n은 2^(LOG2() + 1)) = 2^(2N) 당신이 보여 코드에서
(''FN = f1 n - f2 n'') O (1) 연산이라고 말할 수 있습니다. – BitTickler