STL의 성능 O (LN (N)) 질문

, 누군가가이 explaine 수 있습니다하십시오STL의 성능 O (LN (N)) 질문

을 문서화는 STL의 표준 : : 벡터 = O (LN (N)), 요소 속도의 performace를 찾는 것을 말한다면 무엇을합니까 평균.

O(ln(n)) - "O"은 무엇인가요?

와 나는 다른 STL 컨테이너의 performace에 대해 읽을 수있는

당신에게

2011-02-08 VextoR

http://stackoverflow.com/questions/487258/plain-english-explanation-of-big-o :) – Skurmedel

@aschepler 태그를 추가하면 이름이 지정되므로 이제 설명하는 수많은 질문을 찾을 수 있습니다.) http://stackoverflow.com/questions/tagged/big-o?sort=votes를 참조하십시오. (누군가가 하나를 골라 투표를하면 결정할 필요가 없습니다 ...) – delnan

질문의 두 번째 부분은 다음과 같습니다. http://stackoverflow.com/questions/181693/what-are-the-complexity-guarantees --- 표준 컨테이너 – Skurmedel

Big O notation 알고리즘이의 크기로 확장하는 방법을 측정 할 수있는 방법은 정말입니다 선형 검색을보다 빠르게 수행 그것이 작동하는 데이터가 커집니다.

벡터가 일반적으로 O(n) 인 경우 요소를 찾는 경우 벡터가 정렬되고 binary search family of algorithms 중 하나를 사용하는 경우에만 O(lg(n))입니다.

각 알고리즘의 복잡도는 표준 및 모든 참조 (예 : 위의 std::lower_bound 링크)에서 지정됩니다. BTW

, ln베이스 e에 log이지만, 그것이 O(ln(n))의 말을 기술적으로 정확의 운영 (로그)도 이진 검색은 lg을 수행하지만, 그래서 모든 대수는 같은 복잡하다.

출처

2011-02-08 15:36:11 Motti

기술적으로 측정 값이 아니지만 계산 값입니다 – Falmarri

성능이 아닙니다. 복잡성, 즉 비늘의 정도. 큰 O는 엄격하게 "상한/최악의 경우"에 대해서만 말하고 있습니다. – delnan

@delnan,'O (n) '이 무엇을 의미하는지 모르는 사람에게 _complexity_를 말하는 것은 일종의 재귀를 이해하기 위해 그들이 재귀를 먼저 이해해야한다는 것을 말하는 것과 같습니다. – Motti

큰-O 표기법이 프로그램 성능의 시간 복잡도에 관한 대단히 감사의 preformance.

그래서 O (ln (n))는 벡터가 커질수록 std :: vector의 요소에 액세스하는 것이 ln (size_of_vector)에 비례한다는 것을 의미하지만 이진 검색을 사용하는 정렬 된 벡터에만 해당됩니다. 당신이 두 배 빠른 속도로 가능 요소를 제거하기 때문에 바이너리 검색 따라서 에선이 로그의 기본 2.

http://en.wikipedia.org/wiki/Big_O_notation

출처

2011-02-08 15:36:09 Jordan

O는 big O notation입니다. 알고리즘의 런타임 복잡성을 설명합니다. 본질적으로 대답을 계산하는 데 필요한 작업 수입니다.

출처

2011-02-08 15:36:30 Falmarri

실행 시간 일 필요는 없습니다. big O는 모든 컴퓨팅 리소스를 참조 할 수 있습니다. 기억 –

O는 "주문"의 약자입니다. 그것은 작업의 실행 시간을 측정 한 것입니다.

예를 들어이 코드는 n * n 번 실행되기 때문에 O (n^2)입니다.

int n = 100; 
for (int i = 0; i < n; ++i) { 
    for (int j = 0; j < n; ++j) { 
    } 
}

출처

2011-02-08 15:36:47 dcp

모든 다른 답변은 this로, 괜찮은 참조에 지정된 알고리즘 모양의 전형적인 복잡성을 찾기 위해, O을 정리했다. 각 알고리즘의 맨 아래에 알고리즘의 복잡성이 문서화되어 있습니다.

출처

2011-02-08 15:39:48 Nim

이 가 큰 O 표기법라고도은, 주어진 알고리즘의 일부 파라미터들에 관련하여 점근 복잡도의 표현이다. 점근

우리가 처음 몇 가지 경우에 관심이없는,하지만 알고리즘의 동작에 대한 입력 매개 변수의 크기가 증가하면 것을 의미한다.

파라미터를 측정 할 수있는 알고리즘에 의존

우리

예를 들어, 이진 탐색의 경우에 우리는 비교 수 사이의 관계를 표현에 따라 수행 관련하는 동작 우리가 검색하는 세트의 크기.

실행 시간은 일반적으로이를 통해 추측 할 수 있지만, 특히 구현 또는 하드웨어 제약 조건과 관련하여 올바른 "연산"을 선택하지 않은 경우에는 항상 그렇지 않습니다.

며칠 전에 테이프를 저장소로 사용하여 정렬하는 것에 대한 멋진 게시물이있었습니다. 검색의 복잡성이 비교 횟수를 표현하고 테이프를 저장소로 사용하기 때문에 런타임은 주로 테이프의 움직임에 영향을받습니다 ... 일반적으로 느린 것으로 설명 되더라도 bubblesort가 quicksort보다 성능이 좋음이 밝혀졌습니다.

출처

2011-02-08 16:03:58

STL의 성능 O (LN (N)) 질문

답변

관련 문제