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




빅오 스몰오 (8)

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

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

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

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

참조 :

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


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이 매우 커짐에 따라 변수의 두 함수 (예 : 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)가됩니다.


또한 여러 알고리즘의 복잡성이 둘 이상의 변수, 특히 다차원 문제에 기반한다고 고려하면 가치가 있습니다. 예를 들어, 최근에 다음에 대한 알고리즘을 작성해야했습니다. 주어진 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)입니다. 아래쪽은 밀리미터 단위의 정확도를 가진 실제 좌표를 다루고 있다면 무한한 저장 장치가 필요하다는 것입니다.


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

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


빅 오 (Big-O)에 관해 이야기 할 때 대부분의 사람들이 잊지 않는 한 가지 중요한 사실은 다음과 같습니다.

Big-O를 사용하여 두 알고리즘의 속도 를 비교할 수는 없습니다. Big-O는 처리 된 항목의 수를 두 배로하면 알고리즘이 얼마나 느려지는지 (약), 반으로 잘라내면 얼마나 빨리 처리 할 수 ​​있는지에 대해서만 말합니다.

그러나 완전히 다른 두 알고리즘이 있고 하나 ( A )가 O(n^2) 이고 다른 하나 ( B )가 O(log n) 이면 AB 보다 느리다는 것은 아닙니다. 사실, 100 개의 항목으로, AB 보다 10 배 더 빠를 수 있습니다. 그것은 단지 200 개의 아이템으로, An^2 의 인자에 의해 느리게 성장할 것이고 B 는 인자의 log n 만큼 느리게 성장할 것이라고 말합니다. 예를 들어, A 가 100 개의 항목을 처리 A 데 걸리는 시간과 같은 100 개의 항목에 대해 B 필요한 시간, AB 보다 빠르다는 것을 아는 경우 A 를 추월 할 항목 B 양을 계산할 수 있습니다 A ( B 의 속도가 B 의 속도보다 훨씬 느려지므로 조만간 A 를 추월 할 것입니다. 이것은 확실합니다).


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

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

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

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


위키 백과 .....

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

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

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


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







big-o