Big O 표기법이란 무엇입니까?당신은 그것을 사용합니까?[복제하다]

https://stackoverflow.com/questions/133008

02-07-2019
|

문제

이 질문에는 이미 답변이 있습니다.

"Big O" 표기법에 대한 간단한 영어 설명은 무엇입니까? 답변 39개

Big O 표기법이란 무엇입니까?당신은 그것을 사용합니까?

아무래도 이번 대학 수업을 놓친 것 같아요 :D

누구든지 그것을 사용하고 어디에 사용했는지에 대한 실제 사례를 제공합니까?

또한보십시오:

8세 어린이를 위한 Big-O?
Big O, 어떻게 계산/근사합니까?
계산 복잡도 이론을 실생활에 적용하셨나요?

해결책

대부분의 사람들이 Big-O에 대해 이야기 할 때 잊어 버린 한 가지 중요한 것은 다음을 언급해야한다고 생각합니다.

Big-O를 사용하여 비교할 수 없습니다 속도 두 가지 알고리즘. Big-O는 처리 된 항목 수를 두 배로 늘리면 알고리즘이 얼마나 느리게 얻을 수 있는지 또는 숫자를 반으로 줄이면 얼마나 빠르게 얻을 수 있는지 만 말합니다.

그러나 완전히 다른 두 가지 알고리즘과 하나의 경우 (A) 이다 O(n^2) 그리고 다른 하나 (B) 이다 O(log n), 그것은 말하지 않습니다 A 보다 느립니다 B. 실제로, 100 개의 항목으로 A 보다 10 배 빠를 수 있습니다 B. 200 개 항목만으로도 A 요인에 의해 느리게 성장할 것입니다 n^2 그리고 B 요인에 의해 느리게 성장할 것입니다 log n. 그래서, 당신이 둘 다 벤치마킹하고 얼마나 많은 시간을 알고 있다면 A 100 개의 항목을 처리하는 데 걸리고 시간 B 동일한 100 개의 항목에 대한 필요성 및 A 보다 빠릅니다 B, 당신은 어떤 양의 항목을 계산할 수 있습니다 B 추월 할 것입니다 A 속도로 (속도로 B 중 하나보다 훨씬 느리게 감소합니다 A, 그것은 추월 할 것입니다 A 조만간 - 이것은 확실합니다).

다른 팁

큰 O 표기법은 알고리즘의 제한 계수를 나타냅니다. 입력과 관련하여 알고리즘의 실행 시간이 어떻게 스케일되는지에 대한 단순화 된 표현입니다.

예를 들어 (Java) :

/** Takes an array of strings and concatenates them
  * This is a silly way of doing things but it gets the 
  * point across hopefully
  * @param strings the array of strings to concatenate
  * @returns a string that is a result of the concatenation of all the strings
  *          in the array
  */
public static String badConcat(String[] Strings){
    String totalString = "";
    for(String s : strings) {
        for(int i = 0; i < s.length(); i++){
            totalString += s.charAt(i);
        }
    }
    return totalString;
}

이제 이것이 실제로 무엇을하고 있는지 생각해보십시오. 입력의 모든 특성을 거치고 함께 추가하고 있습니다. 이것은 간단 해 보입니다. 문제는 그 것입니다 문자열은 불변입니다. 따라서 문자열에 문자를 추가 할 때마다 새 문자열을 만들어야합니다. 이렇게하려면 이전 문자열의 값을 새 문자열로 복사하고 새 문자를 추가해야합니다.

이것은 당신이 첫 번째 편지를 복사한다는 것을 의미합니다 N 시간이 어디에 있는지 N 입력의 문자 수입니다. 당신은 캐릭터를 복사 할 것입니다 n-1 시간, 총계가있을 것입니다 (n-1)(n/2) 사본.

이것은 (n^2-n)/2 그리고 큰 O 표기법의 경우, 우리는 가장 높은 크기 계수 만 사용하고 (보통)를 곱한 상수를 삭제하고 O(n^2).

A와 같은 것을 사용합니다 StringBuilder O (nlog (n))의 선을 따라갑니다. 처음에 문자 수를 계산하고의 용량을 설정하면 StringBuilder 당신은 그것을 얻을 수 있습니다 O(n).

따라서 1000 자의 입력 문자가 있다면 첫 번째 예제는 약 백만 개의 작업을 수행 할 것입니다. StringBuilder 10,000을 수행 할 것입니다 StringBuilder ~와 함께 setCapacity 같은 일을하기 위해 1000 개의 작업을 수행합니다. 이것은 거친 추정치이지만 O(n) 표기법은 정확한 런타임이 아닌 크기 순서에 관한 것입니다.

그것은 내가 정기적으로 말한 당시 사용하는 것이 아닙니다. 그러나 무언가를하기위한 최고의 알고리즘을 알아 내려고 할 때 그것은 끊임없이 내 마음의 뒤에 있습니다.

매우 비슷한 질문이 이미 요청되었습니다 8 살짜리 아이를위한 big-o?. 질문에 대한 질문에 대한 질문에 답할 수 있기를 바랍니다.

모든 프로그래머는 큰 O 표기법이 무엇인지, 공통 데이터 구조 및 알고리즘이있는 동작에 적용되는 방법 (따라서 해결하는 문제에 대한 올바른 DS 및 알고리즘을 선택) 및 자체 알고리즘에 대해 계산하는 방법을 알고 있어야합니다.

1) 데이터 구조에서 작업 할 때 알고리즘의 효율성을 측정하는 순서입니다.

2) '추가' / '정렬' / '제거'와 같은 동작은 다른 데이터 구조 (및 알고리즘)에서 다른 시간이 걸릴 수 있습니다. 예를 들어 '추가'및 '찾기'는 해시 맵의 경우 O (1)이지만 o (로그 N) 이진 트리의 경우. 정렬은 QuickSort의 경우 O (nlog n)이지만 일반 배열을 처리 할 때 Bubblesort의 경우 O (N^2)입니다.

3) 알고리즘의 루프 깊이를 보면 계산을 수행 할 수 있습니다. 루프, O (1)은 모든 세트에 반복되는 루프가 없음 O (N). 루프가 각 반복에서 검색 공간을 절반으로 줄인 경우? O (로그 N). 루프 시퀀스를 위해 가장 높은 O ()를 사용하고 루프를 둥지 할 때 O ()에 곱하십시오.

예, 그것보다 더 복잡합니다. 정말로 관심이 있다면 교과서를 받으십시오.

'big-o'표기법은 n이 매우 커짐에 따라 변수 (예 : n)의 두 기능의 성장률을 비교하는 데 사용됩니다. 함수 f가 함수 g보다 훨씬 빨리 자라면 g = o (f)는 충분히 큰 n에 대해 f를 의미한다고 말합니다. 언제나 스케일링 계수까지 G보다 크지 마십시오.

이것은 컴퓨터 과학, 특히 알고리즘 분석에서 매우 유용한 아이디어라는 것이 밝혀졌습니다. 예를 들어 두 가지 다른 알고리즘에 의해 취한 시간을 나타내는 함수의 성장 속도에 정확하게 관심이 있기 때문입니다. 매우 거친, 우리는 런타임 t1 (n)이있는 알고리즘이 런타임 t2 (n)가있는 알고리즘보다 더 효율적이라고 판단 할 수 있습니다. 문제 - 그래프의 배열 길이 또는 그래프의 노드 수와 같은 문제.

N이 규정 된이 규정은 충분히 커지면 유용한 트릭을 많이 당길 수 있습니다. 아마도 가장 자주 사용되는 것은 기능을 가장 빠르게 성장하는 용어로 단순화 할 수 있다는 것입니다. 예를 들어 n^2 + n = o (n^2) N^2 용어가 충분히 커지기 때문에 훨씬 더 큰 n보다 n 용어는 실질적으로 중요하지 않다는 것보다. 그래서 우리는 그것을 고려하지 못할 수 있습니다.

그러나 Big-O 표기법이 작은 N에 덜 유용하다는 것을 의미합니다. 왜냐하면 우리가 잊어 버린 속도가 느리게 성장하는 용어는 여전히 런타임에 영향을 줄 정도로 중요하기 때문입니다.

우리가 지금 가지고있는 것은 두 가지 다른 알고리즘의 비용을 비교하는 도구이며, 하나는 다른 알고리즘보다 빠르거나 느리다고 말하는 속기입니다. Big-O 표기법은 학대 될 수 있으며, 이미 부정확하기 때문에 부끄러운 일입니다! 함수가 다른 기능보다 덜 빠르게 성장하고 두 기능이 동일한 속도로 성장한다고 말하는 동등한 용어가 있습니다.

아, 그리고 내가 그것을 사용합니까? 그렇습니다. 항상-내 코드가 얼마나 효율적인지 알아 내면 비용에 대한 대량의 대략적인 근사치를 제공합니다.

Big-O 뒤에 "직관"

x가 무한대에 접근함에 따라 x에 대한 두 함수 사이의 "경쟁"을 상상해보십시오 : f (x) 및 g (x).

이제 어느 시점에서 (일부 x)에서 한 기능이 항상 더 높은 값을 가지면 다른 기능이 다른 값보다 "더 빠른"이라고 부릅니다.

예를 들어, 모든 x> 100마다 f (x)> g (x)를 보면 f (x)는 g (x)보다 "빠른"것입니다.

이 경우 g (x) = o (f (x))라고 말합니다. F (x)는 g (x)에 대해 일종의 "속도 제한"을 포즈를 취하고 결국 그것을 통과시키고 좋은 것을 위해 남겨두기 때문입니다.

이것은 정확히 정의가 아닙니다 BIG-O 표기법, 또한, F (x)는 일부 상수 C에 대해 C*g (x)보다 커야한다고 말합니다. 일정한 요인 -F (x)는 항상 결국 승리합니다). 공식 정의는 또한 절대 값을 사용합니다. 그러나 나는 그것을 직관적으로 만들었기를 바랍니다.

많은 알고리즘의 복잡성은 특히 다차원 문제에서 하나 이상의 변수를 기반으로한다는 점을 고려할 가치가 있습니다. 예를 들어, 최근에 다음에 대한 알고리즘을 작성해야했습니다. N 포인트 세트와 M 다각형이 주어지면 일부 다각형에있는 모든 점을 추출하십시오. 복잡성은 두 개의 알려진 변수 N과 M을 기반으로하며 각 다각형에 몇 개의 포인트가 있는지 알 수 없습니다. 여기서 큰 o 표기법은 O (f (n)) 또는 O (f (n) + g (m))보다 훨씬 더 관여합니다. 큰 O는 많은 수의 균질 한 품목을 다룰 때 좋지만 항상 이것이 사실이라고 기대하지는 않습니다.

또한 데이터에 대한 실제 반복 수는 종종 데이터에 의존한다는 점도 주목할 가치가 있습니다. QuickSort는 일반적으로 빠르지 만, 전제 데이터를 제공하면 속도가 느려집니다. 내 포인트와 다각형 알로 로리즘은 데이터가 어떻게 구성되었는지에 대한 사전 지식과 n과 m의 상대 크기에 대한 사전 지식을 바탕으로 O (n + (m log (m))에 가까워졌습니다. 다른 상대 크기의 무작위로 구성된 데이터에 대해 잘못.

최종 고려해야 할 것은 알고리즘의 속도와 사용하는 공간의 양 사이에 종종 직접 거래가 있다는 것입니다. 비둘기 구멍 분류 이것의 꽤 좋은 예입니다. 내 포인트와 다각형으로 돌아가서 모든 다각형이 단순하고 빠르게 그리기에 빠졌고, 각각 고정 된 시간 내에 화면에 채워질 수 있다고 가정 해 봅시다. 그래서 내가 검은 색 화면에 M 폴리그를 그리면 O (m) 시간이 걸립니다. 내 N 포인트 중 하나가 다각형인지 확인하려면 그 지점의 픽셀이 녹색인지 검은 색인지 확인합니다. 따라서 점검은 O (N)이고 총 분석은 O (M + N)입니다. 물론 단점은 실제 세계 좌표를 밀리미터 정확도로 다루는 경우 근처에 가까운 저장소가 필요하다는 것입니다 .... ... Ho Hum.

고려해 볼 가치도 있겠네요 상각된 최악의 경우가 아닌 시간.예를 들어, 알고리즘을 실행하면 N 몇 번은 그럴 것이다 오(1) 평균적으로, 때로는 더 나쁠 수도 있습니다.

좋은 예는 기본적으로 요소를 추가할 때 확장되는 배열인 동적 테이블입니다.단순한 구현에서는 요소가 추가될 때마다 배열의 크기가 1씩 증가합니다. 즉, 새 요소가 추가될 때마다 모든 요소를 복사해야 합니다.이로 인해 에²) 이 방법을 사용하여 일련의 배열을 연결하는 경우 알고리즘입니다.대안은 더 많은 스토리지가 필요할 때마다 어레이 용량을 두 배로 늘리는 것입니다.비록 추가가 에) 때로는 복사만 하면 됩니다. 에) 모든 요소 N 요소가 추가되었으므로 작업은 다음과 같습니다. 오(1) 평균적으로.이런 것들이요 스트링빌더 또는 표준::벡터 구현됩니다.

큰 O 표기법은 무엇입니까?

큰 O 표기법은 알고리즘이 입력 데이터의 크기와 관련된 여러 단계 사이의 관계를 표현하는 방법입니다. 이것은 알고리즘 복잡성이라고합니다. 예를 들어 버블 정렬을 사용하여 크기 N 목록을 정렬하면 O (n^2) 단계가 걸립니다.

큰 O 표기법을 사용합니까?

나는 때때로 동료 프로그래머에게 알고리즘 복잡성을 전달하기 위해 큰 O 표기법을 사용합니다. 나는 어떤 알고리즘을 사용할 것인지 생각할 때 항상 기본 이론 (예 : 큰 O 분석 기술)을 사용합니다.

콘크리트 예?

복잡성 분석 이론을 사용하여 메모리 재 할당이 필요하지 않으며 인덱싱을위한 평균 O (N)를 지원하는 효율적인 스택 데이터 구조에 대한 알고리즘을 만들었습니다. 나는 다른 사람들에게 알고리즘을 설명하기 위해 큰 O 표기법을 사용했습니다. 또한 선형 시간 정렬 O (n)가 가능할 때를 이해하기 위해 복잡성 분석을 사용했습니다.

위키피디아에서.....

Big O 표기법은 효율성을 위해 알고리즘을 분석할 때 유용합니다.예를 들어, 크기 n의 문제를 완료하는 데 걸리는 시간(또는 단계 수)은 T(n) = 4n² − 2n + 2일 수 있습니다.

n이 커지면 n² 항이 지배적으로 나타나므로 다른 모든 항은 무시될 수 있습니다. 예를 들어 n = 500일 때 4n² 항은 2n 항의 1000배입니다.후자를 무시하면 대부분의 경우 표현식 값에 거의 영향을 미치지 않습니다.

물론 저는 한번도 써본적이 없습니다..

알고리즘의 복잡성을 평가할 수 있어야합니다. 이것은 얼마나 많은 요소가 취할 것인지에 대한 지식과 결합하여 작업에 적합하지 않은지 판단하는 데 도움이 될 수 있습니다.

최악의 경우 알고리즘이 얼마나 많은 반복을 가지고 있는지를 말합니다.

목록에서 항목을 검색하려면 항목이 생길 때까지 목록을 가로 질러 갈 수 있습니다. 최악의 경우, 아이템은 마지막 장소에 있습니다.

목록에 N 항목이 있다고 가정 해 봅시다. 최악의 경우 반복을 취합니다. 큰 O 공모에서 그것은 O (n)입니다.

그것은 알고리즘이 얼마나 효율적인지 사실이라고 말합니다.

라이센스 : CC-BY-SA ~와 함께 속성

제휴하지 않습니다 StackOverflow