크기가 n = 100 인 알고리즘은 실행하는 데 21 초가 걸립니다. 크기 n = 1000의 경우 31 초가 걸리고 n = 10000의 경우 41 초가 걸립니다. 실행중인 복잡성은 무엇입니까?알고리즘의 시간 복잡도
내가 O (n) 일 때 T (n) = (21 * 1000)/100 = 210s (O (n)이 아님)
O O (log n) = (21 * log1000)/log100 (n) = (21 * 1000^2)/100^2 = 2100 s = 31.5 (Not O (log n))
다른 옵션은 O (1/n)입니다. 어떻게 계산합니까?
은 O(lgn)처럼 보입니다. 로그의베이스 (10)
는 다양한 클래스에서 일부 기능을 플로팅함으로써이 문제를 해결 개시되는 경우는
n의 시간 T(n) = 10*log(n) + 1이다. 예를 들어 O(n) 선형 클래스에 대해 배우려면 T(n)=n을 입력하고 O(n^2) 클래스에 대해 배우려면 T(n)=n^2을 입력하십시오. 이렇게하면 다양한 기능의 모양을 인식하는 데 도움이됩니다.
그런 다음 질문에 주어진 점을 x 축의 n 값과 y 축의 시간 값으로 그립니다. 이 질문에서 모양을 빨리 인식 할 수 있어야합니다.
힌트 : O(log n) :-)
O가 (n)라고 생각합니까? 그래프는 선형입니다. 그러나 내가 공식을 사용할 때 T (n) = (21 * 1000)/100 = 210s가 아닌 31s. – Maria
@Maria 네 생각합니다. 타이밍 데이터만으로는 결코 확신 할 수 없지만 우리가 가진 가장 좋은 추측입니다. 큰 O 표기법을 사용할 때 상수가 "계산되지 않음"을 기억하고 선형 euqation은 "y = kx + m"형식을 가질 수 있습니다. 즉, 상수로 묶인 알고리즘의 "시작 비용"이있을 수 있습니다. 귀하의 계산은 T (0) = 0으로 가정합니다. 항상 0이 아닙니다. 너 알지? 플롯을 다시 확인하십시오. 선은 원래 위치에서 y 축을 자르지 않습니다. – vidstige
* 기타 * Big O 숙제 Maria/Annita? –
예, U는 그것을 풀려고했지만 O (1/n)을 계산하는 방법을 찾을 수 없습니다. 제발 도와 줄 수있어? – Maria
도움이 될 수 있습니다. http://www.perlmonks.org/?node_id=94000 –