큰 O 표기법에 관해서 상수가 중요하지 않은 이유를 간단히 설명해 줄 수 있습니까? 상수를 추가 할 때 복잡성이 그대로 유지되는 이유는 무엇입니까? 이것은 숙제에 관한 질문이 아닙니다.이 점을 더 잘 이해하고 싶습니다. 이 똑바로 큰 O를 갖도록하겠습니다. O가 무한대에 접근함에 따라 함수의 동작을 보는 것입니까?복잡성. 상수는 왜 중요하지 않습니까?
알겠습니다. 모두들 고마워.
복잡성 이론에는 아무런 영향이 없습니다. 입력 크기가 커짐에 따라 함수가 커지는 방식에 관심이 있습니다.
입력 크기가 무한대로 증가함에 따라 상수는 함수가 작동하는 방식에 영향을주지 않습니다.
그러나 특정 코드 조각을 실제로 실행하는 데 관심이있는 경우 크기가 큰 상수 오버 헤드와 기능이 작은 입력 크기에 대해 어떻게 수행되는지 매우 흥미로울 수 있습니다.
복잡성 이론과 실습의 차이점.
Big-O 표기법은 항목 수가 변경되면 리소스 사용 (시간, 메모리)이 어떻게 변경되는지에 대한 것입니다. 예를 들어, 컴퓨터가 1 초에 10 개의 항목을, 4 초에 20 개의 항목을, 9 초에 30 개의 항목을 정렬 할 수있는 경우 O (n ²)입니다.
각각 10 초, 40 초 및 90 초로 동일한 항목을 손으로 정렬 할 수있는 경우 여전히 O (n ²)이지만 일정 상수는 10 배 더 큽니다. 컴퓨터보다 10 배나 오래 걸립니다.
답변은 정의에 의한 것입니다. 일부 기능 f(x)이 일부 기능 g(x)의 big-O 인 경우, f(x)이 일부 상수 시간 g(x)보다 "결국"작다는 것을 의미합니다. (즉, 충분히 큰 경우는 x). 상수의 실제 값은 중요하지 않습니다. "결국"행동의 위치도 마찬가지입니다. - 충분히 큰 경우에 한해서 x과 충분히 큰 상수가 적용된다면, 당신은 보상받을 것입니다.
상수 또는 작은 O가있는 항목을 추가 할 수 있습니다. 중요하지 않습니다. 어떤 용어가 가장 빠르게 성장하고 어느 용어가 지배적인지에 대해서는 x이 커집니다.
Big O는 입력이 커질수록 복잡성이 어떻게 변하는지를 설명합니다. 입력이 커질수록 덜 중요한 상수가됩니다. 예를 들어, 10을 곱하면 n이 1 백만 또는 10 억이 될 때 무언가를 제곱하는 것보다 중요성이 훨씬 적습니다. Big O는 정확한 측정 값이 아닙니다. 알고리즘을 거친 클래스에 넣는 방법입니다. 거대한 n 값에 의미가 없기 때문에 상수를 반올림 할 수 있습니다.
실용 상, 때때로 상수 은과 관련됩니다. 그러나 빅 오 (Big O) 표기법을 말할 때 우리는 점근 적 행동을보고 있습니다. 상수가 점근 거동에 영향을 미치지 않는 이유는 빠르게 커브가 커지는 함수가 일 때 항상이 거대한 상수가있는 경우에도 더 느리게 커브로 함수를 추월하기 때문입니다 (그러나 거기에 도달하는 데 더 오래 걸리지 만, 당연하지).
따라서 우리는 곡선 사이의 점근 관계를 절대로 변화시킬 수 없기 때문에 상수는 "중요하지 않습니다"라고 말합니다.
상수는 N과 관계가 없기 때문에 변경되지 않습니다. 즉 상수입니다. –