가능한 중복은 : Find nearest number in unordered array :
Big O, how do you calculate/approximate it?
Plain English explanation of Big O찾기/방법의 복잡성을 계산
난 그냥이 질문을 보았다. 응답에서 사람들은 제안하는 접근 방식의 복잡성에 대해 이야기하고 있습니다. 그들은 그것을 어떻게 계산합니까? O (n) 또는 O (logn)의 의미는 무엇입니까? 방법/프로그램의 복잡성을 찾고 계산하는 방법?
알고리즘이 n 개의 유사한 요소와 작동 할 때 복잡함이 있습니다. 그리고 n의 변화에 따라 시간이 어떻게 바뀌는 지 말합니다. 따라서 n이 2 번 올라가고 시간이 2 번 오르면 O (n)의 복잡성이 생깁니다.
시간이 (n^2 + 2000n) 함수로 올라가면 복잡성이 다시 O (n^2)라고합니다. 이 이론은 알고리즘의 다른 상수보다 큰 n의 큰 값에 대해서만 생각합니다. 그래서 이론이 항상 당신의 필요에 맞지는 않습니다. 조심하십시오. 알고리즘 이론의 문제는 아니지만 종종 중요한 세부 사항에주의를 기울이지 않는 응용 프로그램의 문제입니다
어떻게 추측 할 수 있습니까? 음, 같은 연산을 n 번 수행하면 n은 배열 요소의 수이고, O (n)입니다. 동일한 조작을 처음 n 번, n-1 번보다 n-2 번에서 1 번까지 수행하면 n + (n-1) + ... + 1의 복잡성을 갖게됩니다. n (n + 1)/2, 다시 const * n + const2 * n^2입니다. 그래서 그것은 O (n^2)입니다. n이 충분히 클 때, 두 번 n은 네 번을 의미 할 것입니다. 논리 및 산수.
이것은 알려진 알고리즘이며 Big O Notation이며 주어진 알고리즘의 계산 시간 복잡도를 찾는 데 사용됩니다. here을 직접 계산하는 방법에 대한 간단한 안내서를 찾을 수 있습니다. 자바가 아니지만 시간 복잡성에 대한 개념은 언어에 무관심하므로 잘해야합니다. 그러나 비슷한 이름을 가진 메소드는 서로 다른 언어에 대해 서로 다른 시간 복잡성을 가질 수 있습니다.
짧은 대답 : O(), o(), 등 ...은 변수에 따라 함수가 커질 추세를 설명하는 표기법입니다. 예 : 성장은 함수에서 가장 높은 다항식 차수에 의해 결정되기 때문에 f (x) = x^2 + x - 6 => O (x^2) 이 특정 항목에 대한 세부 정보 : Big O notation
긴 대답 : 이러한 표기법은 알고리즘 및 계산 이론의 기초가됩니다. 당신은 그것에 관하여 좋은 책을 읽고 싶을지도 모른다. One of the most famous books on Algorithms out there
또한 OpenMIT는 전체 과정을 무료로 제공합니다. 이것은 매우 흥미 롭다!.
http://en.wikipedia.org/wiki/Big_O_notation –
참조 : [Big O에 대한 일반 영어 설명] (http://stackoverflow.com/questions/487258/plain-english-explanation-of-big- O)와 [Big O, 어떻게 계산하시오/근사치입니까?] (http://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it). –
구현 방법을 알고 경험적으로 예측할 수 있으며 응용 프로그램이 실제 데이터로 어떻게 작동하는지 테스트하고 다른 결과를 얻을 수 있습니다. Big-O는 작업량이 증가함에 따라 알고리즘의 복잡성을 비교하는 방법입니다. Big O를 이해하는 것이 유용하지만, 전체 이야기를 말해주지는 않습니다. –