Big O를 사용하여 함수 목록을 나열하십시오.

Question

현재 일부 알고리즘 숙제를 진행 중입니다. 내가하고있는 작업이 올바른지 확인할 수 있도록 몇 가지 질문이 있습니다.

큰 오 표기법에 따라 ~ 20 개의 함수를 비교 한 다음 서로의 빅 시타 인 함수를 그룹화하는 것이 하나의 질문입니다. 그들을 주문하기 위해, 나는 0에서 100까지 각각 하나를 그래프로 찍었고 그래프를 비교하여 어떤 그래프가 다른 그래프보다 좋았는지 찾아 냈습니다. 이것은 올바른 비교 방법입니까? 더 쉬운 방법이 있다면 무엇을 할 수 있습니까? 한 함수가 다른 함수의 큰 시타인지 어떻게 알 수 있습니까? 예를 들어, 내가 지금까지 가지고있는 목록의 작은 부분은 이것이다 :

1/n 

2^100 

log(log(n)) 

n^.5 , 3n^.5 

이 두 그룹화, 그러나 나는 하나가 다른 큰 세타 것을 발견 방법을 정확하게 확실하지 않다 있습니다 .. 그것은 어떤 모든 도움 .. 내가 큰 O, 세타 및 좋아하는 주위에 내 머리를 정리하기 위해 고군분투 감사 나

2^(log(n)), 5n 

에 제안 나의 클래스 메이트였다.

Answer 1

이 표기법은 시간 복잡성 이론과 문제 크기 (즉, '솔루션'공간의 크기)가 입력 매개 변수의 크기에 미치는 영향과 관련이 있습니다.

귀하의 질문은 수학 문제와 관련이 있으며 수학 교환에 더 적합 할 것입니다. 그렇게 말하면, this Wikipedia article은 좋은 출발점입니다.

는 일반적으로 문제점은 (간단한에서 가장 복잡한)로 분할된다 :

• 일정 시간 풀수 - O (1)
• 로그인 시간 풀수 - O (N 로그())
• 다항식 시간 실밥 - O (N^2)
• 슈퍼 실밥 다항식 시간 (보다 자세한 다항식)
• 지수 시간 풀수 - O (N^2 폴리())

,

순위가 결정되는 방식을 결정하려면 집합 N = {1 ... n}을 선택하고이 집합의 각 요소를 각 함수에 연결하고 개별적으로 크기가 커지는 속도를 그립니다.