optimization 스몰오 Big O 표기법이란 무엇입니까? 그것을 사용합니까?




빅오 스몰오 (10)

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

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

나는 내가 추측 한이 대학 수업을 놓쳤다 : D

누구든지 그것을 사용하고 그들이 그것을 사용하는 몇 가지 실제 예제를 제공합니까?

참조 :

8 살짜리 빅 오?
빅 오, 어떻게 계산하시오 / 대략입니까?
실생활에서 계산 복잡성 이론을 적용 했습니까?


빅 오 (Big-O)는 8 세 어린이를 대상 으로 비슷한 질문을 던졌습니다 . . 다행히도 거기에 대한 답변은 귀하의 질문에 대한 답변을 드릴 것입니다. 비록 당신이 더 자세한 설명이 필요하면 그렇게 명확히하지 않았을 수도있는 질문에 대한 약간의 수학 지식이 있습니다.


빅 - 오 뒤에있는 "직관"

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)보다 커야 만한다는 말도 있습니다 (이것은 다른 말로 표현할 수 없습니다). g (x)가 상수 요인을 곱하여 경쟁에서이기도록 돕는다 - f (x)는 항상 결국 승리 할 것이다). 형식 정의는 또한 절대 값을 사용합니다. 그러나 나는 그것을 직관적으로 만들 수 있었으면 좋겠다.


모든 프로그래머는 Big O 표기법, 공통 데이터 구조 및 알고리즘을 사용하는 동작에 적용되는 방식 (그리고 그에 따라 올바른 DS와 알고리즘을 선택하여 문제를 해결 함) 및 자체 알고리즘에 맞게 계산하는 방법을 알고 있어야합니다.

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

2) 'add'/ 'sort'/ 'remove'와 같은 동작은 다른 데이터 구조 (및 알고리즘)를 사용하여 서로 다른 시간을 가질 수 있습니다. 예를 들어, 'add'와 'find'는 해시 맵의 경우 O (1) (로그 n) 이진 트리에 대한. 정렬은 QuickSort의 경우 O (nlog n)이지만 일반 배열을 처리 할 때는 BubbleSort의 경우 O (n ^ 2)입니다.

3) 계산은 일반적으로 알고리즘의 루프 깊이를보고 수행 할 수 있습니다. 루프 없음, O (1), 루프는 모든 세트에서 반복됩니다 (어느 시점에서라도 빠져 나오더라도) O (n). 루프가 각 반복에서 검색 공간을 반으로 줄인다면? O (log n). 일련의 루프에 대해 가장 높은 O ()를 취하고 루프를 중첩 할 때 O ()를 곱하십시오.

네, 그보다 더 복잡합니다. 관심이 있으시다면 교과서 받으십시오.


Big 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;
}

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

즉, 첫 번째 문자를 n 번 복사 할 것입니다. 여기서 n 은 입력 문자 수입니다. 문자를 n-1 번 복사 할 것이므로 총 (n-1)(n/2) 부수가됩니다.

이것은 (n^2-n)/2 이고 Big O 표기법에서는 가장 큰 크기 인자 (일반적으로) 만 사용하고 곱해진 상수는 버리고 O(n^2) 끝납니다.

StringBuilder 와 같은 것을 사용하는 것은 O (nLog (n)) 행을 따릅니다. 처음에 문자 수를 계산하고 StringBuilder 의 용량을 설정하면 O(n) 될 수 있습니다.

그래서 만약 우리가 1000 문자의 입력을 가지고 있다면 첫 번째 예제는 대략 100 만 건의 연산을 수행 할 것이고 StringBuilder 는 10,000 setCapacity 을 수행 할 것이고 setCapacity 가진 StringBuilder 는 똑같은 일을하기 위해 1000 setCapacity 연산을 수행 할 것입니다. 이것은 대략적인 견적이지만 O(n) 표기법은 정확한 실행 시간이 아니라 크기 순서입니다.

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


Big O 표기법이란 무엇입니까?

Big O 표기법은 알고리즘이 입력 데이터의 크기와 관련하여 요구하는 여러 단계 간의 관계를 표현하는 방법입니다. 이를 알고리즘 복잡성이라고합니다. 예를 들어 Bubble Sort를 사용하여 N 크기 목록을 정렬하면 O (N ^ 2) 단계가 필요합니다.

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

동료 프로그래머에게 알고리즘의 복잡성을 전하기 위해 Big O 표기법을 사용합니다. 내가 사용할 알고리즘을 생각할 때, 기본 이론 (예 : Big O 분석 기술)을 사용합니다.

구체적인 예?

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


위키 백과 .....

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

n이 커지면 n² 항이 우세하여 모든 다른 항이 무시 될 수 있습니다. 예를 들어 n = 500, 4n² 항은 2n 항의 1000 배입니다. 후자를 무시하면 대부분의 경우 표현의 가치에 미미한 영향을 미칩니다.

분명히 나는 ​​그것을 사용한 적이 없다 ..


또한 최악의 경우보다는 상각 된 시간을 고려해 볼 가치가 있습니다. 예를 들어 알고리즘을 n 번 실행하면 평균적으로 O (1)이 되지만 가끔 더 나 빠질 수 있습니다.

좋은 예가 동적 테이블입니다. 기본적으로 요소를 추가 할 때 확장되는 배열입니다. 순진한 구현은 추가 된 각 요소에 대해 배열 크기를 1 씩 증가시킵니다. 즉, 새 요소가 추가 될 때마다 모든 요소를 ​​복사해야합니다. 이 방법을 사용하여 일련의 배열을 연결하면 O (n 2 ) 알고리즘이됩니다. 대안은 더 많은 스토리지가 필요할 때마다 어레이의 용량을 두 배로 늘리는 것입니다. 추가가 O (n) 연산 인 경우에도 추가 된 n 개 요소마다 O (n) 개의 요소 만 복사하면되므로 평균 O (1) 회가 됩니다. 이것은 StringBuilderstd :: vector 같은 것들이 구현되는 방법입니다.


알고리즘은 최악의 경우 알고리즘이 얼마나 많은 반복을하는지 나타냅니다.

목록에서 항목을 검색하려면 해당 항목을 찾을 때까지 목록을 탐색 할 수 있습니다. 최악의 경우 항목은 마지막 위치에 있습니다.

목록에 n 개의 항목이 있다고 가정 해 보겠습니다. 최악의 경우에 n 회 반복합니다. Big O notiation에서는 O (n)입니다.

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


또한 여러 알고리즘의 복잡성이 둘 이상의 변수, 특히 다차원 문제에 기반한다고 고려하면 가치가 있습니다. 예를 들어, 최근에 다음에 대한 알고리즘을 작성해야했습니다. 주어진 n 개의 점과 m 개의 다각형 집합이 주어지면 다각형에있는 모든 점을 추출합니다. 복잡성은 두 개의 알려진 변수 인 n과 m을 기반으로하며 각 폴리곤에 얼마나 많은 점이 있는지 알 수 없습니다. 큰 O 표기법은 O (f (n)) 또는 O (f (n) + g (m))보다 훨씬 더 복잡합니다. 큰 O는 많은 양의 균질 한 아이템을 다룰 때 좋지만, 항상 그렇다고 기대하지는 마십시오.

또한 데이터에 대한 실제 반복 횟수는 종종 데이터에 따라 다릅니다. Quicksort는 일반적으로 빠르지 만 미리 정렬 된 데이터를 제공하면 속도가 느려집니다. 내 포인트와 폴리곤 alogorithm은 데이터가 어떻게 구성 될 것인가에 대한 사전 지식과 n과 m의 상대적인 크기에 기초하여 O (n + (m log (m))에 가깝게 매우 빠르게 끝났다. 서로 다른 크기의 무작위로 구성된 데이터에 심하게 있습니다.

고려해야 할 마지막 사항은 알고리즘의 속도와 사용되는 공간의 양 사이에 직접적인 상충 관계가있는 경우가 종종 있습니다. 비둘기 구멍 정렬 은 이것의 좋은 예입니다. 내 포인트와 폴리곤으로 돌아가서, 모든 폴리곤은 간단하고 빠르게 그리기가 가능하다고 말하면서, 스크린 상에, 즉 파란색으로, 일정한 시간 내에 채울 수 있습니다. 그래서 검은 화면에 m 개의 다각형을 그려 넣으면 O (m) 시간이 걸릴 것입니다. 내 n 점 중 하나가 다각형에 있는지 확인하려면 해당 점의 픽셀이 녹색인지 검은 색인지 여부 만 확인하면됩니다. 따라서 수표는 O (n)이고, 전체 분석은 O (m + n)입니다. 아래쪽은 밀리미터 단위의 정확도를 가진 실제 좌표를 다루고 있다면 무한한 저장 장치가 필요하다는 것입니다.


'Big-O'표기법은 n이 매우 커짐에 따라 변수의 두 함수 (예 : n)의 성장률을 비교하는 데 사용됩니다. 함수 f가 함수 g보다 훨씬 빠르게 성장하면 g = O (f)라고 말하면 충분히 큰 n에 대해 f가 항상 g보다 스케일링 팩터보다 크다는 것을 의미합니다.

알고리즘은 컴퓨터 과학, 특히 알고리즘 분석에서 매우 유용한 아이디어 인 것으로 나타났습니다. 왜냐하면 우리는 종종 서로 다른 두 알고리즘에 의해 취해진 시간을 나타내는 함수의 증가율에 정확하게 관련되어 있기 때문입니다. 매우 조악하게, 우리는 실행 시간 t1 (n)의 알고리즘이 실행 시간 t2 (n)의 알고리즘보다 더 효율적이라는 것을 결정할 수 있습니다. 충분히 큰 n에 대해 t1 = O (t2)이면 일반적으로 '크기' 문제는 배열의 길이 나 그래프에있는 노드의 수 또는 무엇이든간에.

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

그러나 우리가 잊어 버린 느린 성장 조건은 런타임에 영향을 줄만큼 여전히 중요하기 때문에 big-O 표기법이 작은 n에 덜 유용하다는 것을 의미합니다.

지금 우리가 가지고있는 것은 두 개의 서로 다른 알고리즘의 비용을 비교하는 도구이며, 하나가 다른 것보다 더 빠르거나 느리다는 것을 나타내는 단축형입니다. 빅 오 (Big-O) 표기법은 학대 당할 수 있습니다. 이미 충분히 부정확합니다! 함수가 다른 것보다 빠르게 성장하지 않으며 두 함수가 같은 속도로 증가한다고 말하는 것과 동등한 용어가 있습니다.

오, 내가 그것을 사용합니까? 예, 항상 - 코드가 얼마나 효율적인 지 알아 내면 비용에 대한 대략적인 백 - 오버 (back-of-the-envelope)가됩니다.







big-o