"Big O" 표기법에 대한 일반 영어 설명은 무엇입니까?

질문자 :Arec Barrwin

나는 가능한 한 적은 형식적인 정의와 간단한 수학을 선호합니다.

답변자 : cletus

빠른 메모, 내 대답은 Big Oh 표기법 (상한선)과 Big Oh 표기법 "Θ"(양측 경계선)을 혼동하는 것이 거의 확실합니다. 그러나 내 경험에 따르면 이것은 실제로 비학문적 환경에서 토론하는 전형입니다. 혼란을 드려 죄송합니다.

---

BigOh 복잡성은 다음 그래프로 시각화할 수 있습니다.

Big Oh 표기법에 대해 내가 줄 수 있는 가장 간단한 정의는 다음과 같습니다.

Big Oh 표기법은 알고리즘의 복잡성을 상대적으로 표현한 것입니다.

그 문장에는 중요하고 의도적으로 선택된 단어가 있습니다.

• 상대: 사과와 사과만 비교할 수 있습니다. 산술 곱셈을 수행하는 알고리즘을 정수 목록을 정렬하는 알고리즘과 비교할 수 없습니다. 그러나 산술 연산(곱하기 하나, 더하기 하나)을 수행하는 두 알고리즘을 비교하면 의미 있는 것을 알 수 있습니다.
• 표현: BigOh(가장 간단한 형태)는 알고리즘 간의 비교를 단일 변수로 줄입니다. 해당 변수는 관찰 또는 가정을 기반으로 선택됩니다. 예를 들어, 정렬 알고리즘은 일반적으로 비교 작업(상대 순서를 결정하기 위해 두 노드를 비교)을 기반으로 비교됩니다. 이것은 비교가 비싸다고 가정합니다. 그러나 비교는 저렴하지만 스와핑은 비싸다면 어떻게 될까요? 비교를 변경합니다. 그리고
• 복잡성: 10,000개의 요소를 정렬하는 데 1초가 걸린다면 백만 개를 정렬하는 데 얼마나 걸립니까? 이 경우 복잡성은 다른 것에 대한 상대적 척도입니다.

나머지 부분을 다 읽었으면 돌아와서 위의 내용을 다시 읽으십시오.

내가 생각할 수 있는 BigOh의 가장 좋은 예는 산수를 하는 것입니다. 두 개의 숫자(123456 및 789012)를 사용합니다. 학교에서 배운 기본 산술 연산은 다음과 같습니다.

• 덧셈;
• 빼기;
• 곱셈; 그리고
• 분할.

이들 각각은 작업 또는 문제입니다. 이를 해결하는 방법을 알고리즘 이라고 합니다.

덧셈이 가장 간단합니다. 숫자를 (오른쪽으로) 정렬하고 결과에서 해당 덧셈의 마지막 숫자를 쓰는 열에 숫자를 추가합니다. 해당 숫자의 '십' 부분은 다음 열로 이월됩니다.

이 숫자를 더하는 것이 이 알고리즘에서 가장 비용이 많이 드는 작업이라고 가정해 보겠습니다. 이 두 숫자를 더하려면 6자리를 더해야 합니다(7번째 숫자도 가능). 100자리 숫자 두 개를 더하면 100개 더해야 합니다. 10,000자리 숫자 두 개를 더하면 10,000개를 더해야 합니다.

패턴이 보이시나요? 복잡성 (연산 횟수)은 큰 수 의 자릿수 n에 정비례합니다. 이것을 O(n) 또는 선형 복잡성이라고 합니다.

뺄셈도 비슷합니다(캐리 대신 빌릴 필요가 있는 경우 제외).

곱셈은 다릅니다. 숫자를 정렬하고 맨 아래 숫자의 첫 번째 숫자를 취하여 맨 위 숫자의 각 숫자에 차례로 곱하는 식으로 각 숫자에 대해 반복합니다. 따라서 두 개의 6자리 숫자를 곱하려면 36개의 곱셈을 수행해야 합니다. 최종 결과를 얻기 위해 10개 또는 11개 열 추가를 수행해야 할 수도 있습니다.

두 개의 100자리 숫자가 있는 경우 10,000개의 곱셈과 200개의 더하기를 수행해야 합니다. 2백만 자리 숫자에 대해 1조(10 ¹² ) 곱셈과 2백만 덧셈을 수행해야 합니다.

알고리즘이 n- 제곱으로 확장됨에 따라 이것은 O(n ² ) 또는 2차 복잡도 입니다. 이것은 또 다른 중요한 개념을 소개하기에 좋은 시간입니다.

우리는 복잡성의 가장 중요한 부분에만 신경을 씁니다.

^{똑똑한 사람은 연산 수를 n 2} + 2n으로 표현할 수 있다는 것을 깨달았을 것입니다. 그러나 각각 백만 자릿수 두 개의 숫자가 있는 예에서 보았듯이 두 번째 항(2n)은 중요하지 않게 됩니다(해당 단계에서 전체 연산의 0.0002%를 차지함).

여기에서 최악의 시나리오를 가정했음을 알 수 있습니다. 6자리 수를 곱할 때 그 중 하나가 4자리이고 다른 하나가 6자리이면 곱셈은 24개뿐입니다. 여전히 우리는 'n'에 대한 최악의 시나리오를 계산합니다. 즉, 둘 다 6자리 숫자일 때입니다. 따라서 Big Oh 표기법은 알고리즘의 최악의 시나리오에 관한 것입니다.

전화번호부

내가 생각할 수 있는 다음으로 가장 좋은 예는 일반적으로 White Pages 또는 이와 유사한 전화번호부이지만 국가마다 다릅니다. 그러나 나는 사람들을 성을 기준으로 나열한 다음 이니셜이나 이름, 아마도 주소, 전화번호 순으로 나열하는 것에 대해 이야기하고 있습니다.

이제 컴퓨터에 1,000,000명의 이름이 포함된 전화번호부에서 "John Smith"의 전화번호를 찾도록 지시한다면 어떻게 하시겠습니까? S가 얼마나 시작되었는지 추측할 수 있다는 사실을 무시하고(당신이 할 수 없다고 가정해 봅시다), 당신은 무엇을 하시겠습니까?

일반적인 구현은 중간까지 열어서 500,000 ^번째 를 "Smith"와 비교하는 것일 수 있습니다. "Smith, John"이 발생하면 정말 운이 좋은 것입니다. "John Smith"가 그 이름 앞이나 뒤에 있을 가능성이 훨씬 더 높습니다. 그 이후라면 전화번호부의 마지막 절반을 반으로 나누고 반복합니다. 그 이전이라면 전화번호부의 전반부를 반으로 나누고 반복합니다. 등등.

이것을 이진 검색 이라고 하며 인식 여부에 관계없이 프로그래밍에서 매일 사용됩니다.

따라서 백만 명의 이름이 있는 전화번호부에서 이름을 찾으려면 실제로 이 작업을 최대 20번 수행하여 아무 이름이나 찾을 수 있습니다. 검색 알고리즘을 비교할 때 우리는 이 비교가 우리의 'n'이라고 결정합니다.

• 이름이 3개인 전화번호부의 경우 최대 2번의 비교가 필요합니다.
• 7의 경우 최대 3이 걸립니다.
• 15의 경우 4가 걸립니다.
• …
• 1,000,000에는 20이 걸립니다.

정말 놀랍지 않나요?

BigOh 용어로 이것은 O(log n) 또는 대수 복잡도 입니다. 이제 문제의 로그는 ln(base e), log ₁₀ , log ₂ 또는 다른 밑이 될 수 있습니다. ^{O(2n 2} ) 및 O(100n ² )이 여전히 둘 다 O(n ² )인 것처럼 여전히 O(log n)인 것은 중요하지 않습니다.

이 시점에서 BigOh를 알고리즘으로 세 가지 경우를 결정하는 데 사용할 수 있음을 설명하는 것이 좋습니다.

• 최상의 경우: 전화번호부 검색에서 가장 좋은 경우는 하나의 비교에서 이름을 찾는 것입니다. 이것은 O(1) 또는 상수 복잡성입니다 .
• 예상 사례: 위에서 논의한 바와 같이 이것은 O(log n)입니다. 그리고
• 최악의 경우: 이것은 또한 O(log n)입니다.

일반적으로 우리는 최상의 경우에 대해 신경 쓰지 않습니다. 우리는 예상되는 최악의 경우에 관심이 있습니다. 때로는 이들 중 하나가 더 중요할 것입니다.

전화번호부로 돌아갑니다.

전화번호가 있고 이름을 찾고 싶다면? 경찰은 역 전화번호부를 가지고 있지만 그러한 조회는 일반 대중에게 거부됩니다. 아니면 그들은? 기술적으로 일반 전화번호부에서 조회 번호를 반대로 할 수 있습니다. 어떻게?

이름에서 시작하여 숫자를 비교합니다. 일치하면 훌륭하고 일치하지 않으면 다음으로 넘어갑니다. 전화번호부는 순서 가 없기 때문에(어쨌든 전화번호로) 이렇게 해야 합니다.

따라서 전화번호가 주어진 이름을 찾으려면(역방향 조회):

• 최상의 경우: O(1);
• 예상 사례: O(n)(500,000의 경우); 그리고
• 최악의 경우: O(n)(1,000,000의 경우).

여행하는 세일즈맨

이것은 컴퓨터 과학에서 꽤 유명한 문제이며 언급할 가치가 있습니다. 이 문제에는 N 개의 마을이 있습니다. 각 마을은 일정 거리의 도로로 하나 이상의 다른 마을과 연결되어 있습니다. 여행하는 세일즈맨 문제는 모든 도시를 방문하는 가장 짧은 여행을 찾는 것입니다.

간단하게 들리나요? 다시 생각 해봐.

모든 쌍 사이에 도로가 있는 3개의 마을 A, B, C가 있는 경우 다음을 수행할 수 있습니다.

• A → B → C
• A → C → B
• B → C → A
• B → A → C
• C → A → B
• C → B → A

글쎄, 실제로 이들 중 일부는 동일하기 때문에 그보다 적습니다(예를 들어, 동일한 도로를 역방향으로 사용하기 때문에 A → B → C 및 C → B → A는 동일합니다).

실제로는 3가지 가능성이 있습니다.

• 이것을 4개의 마을로 가져가면 (iirc) 12개의 가능성이 있습니다.
• 5로 하면 60입니다.
• 6은 360이 됩니다.

이것은 factorial 이라는 수학 연산의 함수입니다. 원래:

• 5! = 5 × 4 × 3 × 2 × 1 = 120
• 6! = 6 × 5 × 4 × 3 × 2 × 1 = 720
• 7! = 7 × 6 × 5 × 4 × 3 × 2 × 1 = 5040
• …
• 25! = 25 × 24 × … × 2 × 1 = 15,511,210,043,330,985,984,000,000
• …
• 50! = 50 × 49 × … × 2 × 1 = 3.04140932 × 10 ⁶⁴

따라서 여행하는 세일즈맨 문제의 BigOh는 O(n!) 또는 계승 또는 조합 복잡성 입니다.

200개 마을에 도착할 때쯤이면 우주에 기존 컴퓨터의 문제를 해결할 시간이 충분하지 않습니다.

생각해 볼 것이 있습니다.

다항식 시간

내가 빠르게 언급하고 싶은 또 다른 요점은 O(n ^a ) 의 복잡성을 갖는 알고리즘은 다항식 복잡성 을 갖 거나 다항식 시간에 풀 수 있다는 것입니다.

O(n), O(n ² ) 등은 모두 다항식 시간입니다. 일부 문제는 다항식 시간에 풀 수 없습니다. 이 때문에 세계에서 어떤 것들이 사용됩니다. 공개 키 암호화 가 대표적인 예입니다. 매우 큰 수의 두 소인수를 찾는 것은 계산적으로 어렵습니다. 그렇지 않으면 우리가 사용하는 공개 키 시스템을 사용할 수 없습니다.

어쨌든, 그것이 BigOh(개정)에 대한 나의 (평범한 영어) 설명을 위한 것입니다.

답변자 : Ray Hidayat

알고리즘이 입력 크기에 따라 어떻게 확장되는지 보여줍니다.

O(n ² ) : 2차 복잡성으로 알려짐

• 1개 항목: 1개 작업
• 10개 항목: 100개 작업
• 100개 항목: 10,000개 작업

항목 수는 10배 증가하지만 시간은 10 ² 배 증가합니다. 기본적으로 n=10이므로 O(n ² ) 는 10 ^{2 인} 배율 인수 n ² 를 제공합니다.

O(n) : 선형 복잡성으로 알려짐

• 1개 항목: 1초
• 10개 항목: 10초
• 100개 항목: 100초

이번에는 항목 수가 10배 증가하고 시간도 증가합니다. n=10이므로 O(n)의 스케일링 계수는 10입니다.

O(1) : 상수 복잡성으로 알려짐

• 1개 항목: 1개 작업
• 10개 항목: 1개 작업
• 100개 항목: 1개 작업

항목 수는 여전히 10배 증가하지만 O(1)의 배율 인수는 항상 1입니다.

O(log n) : 대수 복잡성으로 알려짐

• 1개 항목: 1개 작업
• 10개 항목: 2개 작업
• 100개 항목: 3개 작업
• 1000개 항목: 4개 작업
• 10,000개 항목: 5개 작업

연산 횟수는 입력 값의 로그만큼만 증가합니다. 따라서 이 경우 각 계산에 1초가 걸린다고 가정하면 입력 n 의 로그가 필요한 시간이므로 log n 입니다.

그것이 요지입니다. 그들은 수학을 줄여 정확히 n ² 또는 그들이 말하는 것이 아닐 수도 있지만 스케일링에서 지배적인 요소가 될 것입니다.

답변자 : Community Wiki

Big-O 표기법("점근적 성장" 표기법이라고도 함)은 원점 근처의 상수 요소와 항목을 무시할 때 기능이 "모양"으로 표시되는 것 입니다. 우리는 사물의 규모 에 대해 이야기하기 위해 그것을 사용합니다.

---

기초

"충분히" 큰 입력을 위해...

• f(x) ∈ O(upperbound) 은 f 상한보다 "더 빠르게 성장하지 않음"을 upperbound
• f(x) ∈ Ɵ(justlikethis) 평균 f "똑같이 증가" justlikethis
• f(x) ∈ Ω(lowerbound) 은 f 가 "하한보다 느리게 성장하지 않음"을 lowerbound

big-O 표기법은 상수 요인을 고려하지 않습니다. 함수 9x² 는 10x²와 같이 "정확히 성장" 10x² 합니다. 기능 : 둘 다 ( "문제의 크기가 작은 경우 어떻게됩니까" "기원 근처 물건"또는) 비 점근 물건에 대해 큰-O 점근 표기법 치료를하지 않습니다 10x² 로 말한다는 "정확히 같은 성장" 10x² - x + 2 .

방정식의 작은 부분을 무시하려는 이유는 무엇입니까? 더 크고 더 큰 규모를 고려할 때 방정식의 큰 부분에 의해 완전히 왜소해지기 때문입니다. 그들의 기여는 왜소하고 무의미해집니다. (예시 섹션을 참조하십시오.)

다시 말해서 무한대로 가는 비율 에 관한 것입니다. 실제 걸리는 시간을 O(...) 나누면 큰 입력의 한계에서 상수 인수를 얻게 됩니다. 직관적으로 이것은 의미가 있습니다. 하나를 곱하여 다른 하나를 얻을 수 있으면 함수가 서로 "크기 조정"됩니다. 그 때 우리가 말하는 ...

 actualAlgorithmTime(N) ∈ O(bound(N)) eg "time to mergesort N elements is O(N log(N))"

... 이것은 "충분히 큰" 문제 크기 N (원점 근처의 항목을 무시하는 경우)에 대해 다음과 같은 상수(예: 2.5, 완전히 구성된)가 있음을 의미합니다.

 actualAlgorithmTime(N) eg "mergesort_duration(N) " ────────────────────── < constant ───────────────────── < 2.5 bound(N) N log(N)

상수에는 많은 선택이 있습니다. 종종 "최상의" 선택은 알고리즘의 "상수 요인"으로 알려져 있습니다... 그러나 우리는 종종 가장 크지 않은 항을 무시하는 것처럼 이를 무시합니다(보통 중요하지 않은 이유는 상수 요인 섹션 참조). 위의 방정식을 경계로 생각할 수도 있습니다. " 최악의 시나리오에서 걸리는 시간은 인수 2.5 내에서 N*log(N) t는 많이 신경 쓰지 않는다) ".

일반적으로 O(...) 는 최악의 경우 동작에 관심을 갖기 때문에 가장 유용한 것입니다. f(x) 가 프로세서 또는 메모리 사용과 같은 "나쁜" 것을 나타내는 경우 f(x) ∈ O(upperbound) "는 " upperbound 이 프로세서/메모리 사용의 최악의 시나리오"를 의미합니다.

---

애플리케이션

순전히 수학적 구조로서 big-O 표기법은 처리 시간과 메모리에 대한 이야기에만 국한되지 않습니다. 다음과 같이 스케일링이 의미 있는 모든 것의 점근론을 논의하는 데 사용할 수 있습니다.

• 파티에서 N 명의 가능한 핸드셰이크의 수 Ɵ(N²) , 특히 N(N-1)/2 , 그러나 중요한 것은 N² )
• 시간의 함수로 일부 바이러스성 마케팅을 본 사람들의 확률적 예상 수
• CPU, GPU 또는 컴퓨터 클러스터의 처리 장치 수에 따라 웹 사이트 대기 시간이 확장되는 방식
• 트랜지스터 수, 전압 등의 함수로 CPU 다이에서 열 출력이 확장되는 방식
• 입력 크기의 함수로 알고리즘을 실행해야 하는 시간
• 입력 크기의 함수로 알고리즘을 실행하는 데 필요한 공간

---

예시

위의 악수 예에서 방에 있는 모든 사람이 다른 사람과 악수합니다. 이 예에서 #handshakes ∈ Ɵ(N²) . 왜요?

약간 백업: 악수 횟수는 정확히 n-choose-2 또는 N*(N-1)/2 (각 N명의 사람들은 N-1명의 다른 사람들과 악수하지만 이것은 악수를 두 번 계산하므로 다음으로 나눕니다. 2):

그러나 매우 많은 수의 사람들의 경우 선형 항 N 은 왜소하고 효과적으로 비율에 0을 기여합니다(차트에서: 전체 상자에 대한 대각선의 빈 상자 비율은 참가자 수가 많을수록 작아집니다). 따라서 스케일링 동작은 order N² 또는 핸드셰이크 수가 "N²처럼 늘어납니다"입니다.

 #handshakes(N) ────────────── ≈ 1/2 N²

차트의 대각선에 빈 상자(N*(N-1)/2 체크 표시)가 없는 것과 같습니다( ^{점근적으로 N 2} 체크 표시).

("일반 영어"에서 임시 탈선:) 이것을 스스로 증명하고 싶다면 비율에 대한 간단한 대수학을 수행하여 여러 항으로 나눌 수 있습니다( lim 은 "한계에서 고려됨"을 의미합니다. 당신은 그것을 본 적이 없습니다, 그것은 단지 "그리고 N은 정말 정말 큽니다"에 대한 표기법입니다):

 N²/2 - N/2 (N²)/2 N/2 1/2 lim ────────── = lim ( ────── - ─── ) = lim ─── = 1/2 N→∞ N² N→∞ N² N² N→∞ 1 ┕━━━┙ this is 0 in the limit of N→∞: graph it, or plug in a really large number for N

tl;dr: 핸드셰이크의 수는 x²가 너무 커서 #handshakes/x² 비율을 기록하면 정확히 x² 핸드셰이크가 필요하지 않다는 사실조차 표시되지 않습니다. 임의의 큰 동안 십진수로.

예: x=1million의 경우 #handshakes/x² 비율: 0.499999...

---

직관 구축

이렇게 하면 다음과 같은 진술을 할 수 있습니다.

" 충분히 큰 inputsize = N 에 대해 상수 요소가 무엇이든 입력 크기를 두 배로 늘리면 ...

• ... O(N)("선형 시간") 알고리즘에 걸리는 시간을 두 배로 늘립니다."

N → (2N) = 2( N )

• ... 나는 O(N²)("2차 시간") 알고리즘이 걸리는 시간을 두 제곱(4배)합니다." (예: 문제가 100배 큰 문제는 100²=10000배의 시간이 걸립니다... 아마도 지속 불가능할 수 있음)

N² → (2N)² = 4( N² )

• ... 나는 O(N³)("입방 시간") 알고리즘이 걸리는 시간을 두 배로 제곱(8진수)합니다." (예: 문제가 100x만큼 크면 100³=1000000x만큼 오래 걸립니다... 매우 지속 불가능함)

cN³ → c(2N)³ = 8( cN³ )

• ... O(log(N)) ("logarithmic time") 알고리즘이 걸리는 시간에 고정된 양을 추가합니다." (저렴합니다!)

c log(N) → c log(2N) = (c log(2))+( c log(N) ) = (고정량)+( c log(N) )

• ... 나는 O(1)("일정 시간") 알고리즘이 걸리는 시간을 변경하지 않습니다." (가장 저렴합니다!)

c*1 → c*1

• ... 나는 O(N log(N)) 알고리즘이 소요되는 시간을 "(기본적으로) 두 배로" 합니다." (상당히 일반적)

c 2N log(2N) / c N log(N) (여기서 f(2n)/f(n)을 나누지만 위와 같이 식을 마사지하고 위와 같이 cNlogN을 인수분해할 수 있음)
→ 2로그(2N)/로그(N)
→ 2 (log(2) + log(N))/log(N)
→ 2*(1+(log ₂ N) ^-1 ) (큰 N의 경우 기본적으로 2, 결국 2.000001 미만)
(또는 log(N)은 데이터에 대해 항상 17보다 낮으므로 선형인 O(17 N)입니다. 엄격하거나 의미가 없습니다.)

• ... 나는 O(2 ^N ) ( "지수 시간") 알고리즘이 걸리는 시간을 엄청나게 늘립니다." (문제를 단일 단위로 증가시키면 시간이 두 배(또는 세 배 등) 증가할 것입니다)

2 ^N → 2 ^2N = (4 ^N )........... 다른 식으로 말하면...... 2 ^N → 2 ^N+1 = 2 ^N 2 ¹ = 2 2 ^N

[수학적 경향이 있는 경우 사소한 사이드노트에 대한 스포일러 위에 마우스를 놓을 수 있습니다.]

(https://stackoverflow.com/a/487292/711085에 대한 크레딧 포함)

(기술적으로 상수 요소는 좀 더 난해한 예에서 중요할 수 있지만 위의 내용(예: log(N)에서)을 그렇게 표현하지 않았습니다)

이것은 프로그래머와 응용 컴퓨터 과학자들이 기준점으로 사용하는 빵과 버터의 성장 순서입니다. 그들은 항상 이것들을 봅니다. (따라서 기술적으로 "입력을 두 배로 늘리면 O(√N) 알고리즘이 1.414배 느려진다"라고 생각할 수 있지만 "이것은 대수보다는 나쁘지만 선형보다 낫다"라고 생각하는 것이 좋습니다.)

---

상수 요인

일반적으로 우리는 특정 상수 요인이 무엇인지 신경 쓰지 않습니다. 왜냐하면 그것들은 함수가 성장하는 방식에 영향을 미치지 않기 때문입니다. 예를 들어, 두 알고리즘 모두 O(N) 시간이 걸릴 수 있지만 하나는 다른 것보다 두 배 느릴 수 있습니다. 최적화는 까다로운 비즈니스이기 때문에 요소가 매우 크지 않으면 일반적으로 너무 많이 신경 쓰지 않습니다(최적화는 시기상조입니까? ). 또한 더 나은 big-O로 알고리즘을 선택하는 것만으로도 성능이 크게 향상되는 경우가 많습니다.

일부 점근적으로 우수한 알고리즘(예: 비비교 O(N log(log(N))) 정렬)은 상수 인수(예: 100000*N log(log(N)) )가 너무 크거나 상대적으로 큰 오버헤드를 가질 수 있습니다. O(N log(log(N))) 과 같이 숨겨진 + 100*N 과 같이 "빅 데이터"에서도 거의 사용할 가치가 없습니다.

---

때때로 O(N)이 최선의 방법인 이유, 즉 데이터 구조가 필요한 이유

O(N) 알고리즘은 모든 데이터를 읽어야 하는 경우 어떤 의미에서 "최고의" 알고리즘입니다. 많은 양의 데이터 를 읽는 바로 그 행위가 O(N) 연산입니다. 메모리에 로드하는 것은 일반적으로 O(N) (또는 하드웨어 지원이 있는 경우 더 빠르거나 데이터를 이미 읽은 경우 전혀 시간이 없음). 그러나 모든 데이터 조각(또는 다른 모든 데이터 조각)을 만지거나 보는 경우 알고리즘이 이 보기를 수행하는 O(N) 실제 알고리즘이 얼마나 오래 걸리든 모든 데이터를 살펴보는 데 그 시간을 소비했기 때문에 O(N)

글을 쓰는 행위 자체에 대해서도 마찬가지입니다. N개의 항목을 출력하는 모든 알고리즘은 출력이 최소한 그만큼 길기 때문에 N 시간이 걸립니다(예: N 카드 세트의 모든 순열(재배열 방법)을 출력하는 것은 계승적입니다. O(N!) (이것이 바로 그 이유입니다. 경우에 따라 좋은 프로그램은 반복이 O(1) 메모리를 사용하고 모든 중간 단계를 인쇄하거나 저장하지 않도록 합니다.

이것은 데이터 구조를 사용하도록 동기를 부여합니다. 데이터 구조는 데이터를 한 번만(보통 O(N) 시간) 읽고 임의의 양의 전처리(예: O(N) 또는 O(N log(N)) 또는 O(N²) ) 우리는 이를 작게 유지하려고 합니다. 그 후 데이터 구조(삽입/삭제 등)를 수정하고 데이터에 대한 쿼리를 수행하는 데 O(1) 또는 O(log(N)) 와 같이 시간이 거의 걸리지 않습니다. 그런 다음 많은 수의 쿼리를 진행합니다! 일반적으로 미리 하고자 하는 작업이 많을수록 나중에 해야 하는 작업이 줄어듭니다.

예를 들어 수백만 개의 도로 세그먼트의 위도 및 경도 좌표가 있고 모든 교차로를 찾고 싶다고 가정해 보겠습니다.

• 순진한 방법: 거리 교차로의 좌표가 있고 인근 거리를 조사하려면 매번 수백만 개의 세그먼트를 살펴보고 각 세그먼트의 인접성을 확인해야 합니다.
• 이 작업을 한 번만 수행해야 하는 경우 O(N) 의 순진한 방법을 한 번만 수행하면 문제가 되지 않지만 여러 번(이 경우 N 번, 각 세그먼트), O(N²) 작업 또는 1000000²=1000000000000 작업을 수행해야 합니다. 좋지 않습니다(현대 컴퓨터는 초당 약 10억 개의 작업을 수행할 수 있음).
• 해시 테이블(즉시 속도 조회 테이블, 해시맵 또는 사전이라고도 함)이라는 간단한 구조를 사용하는 경우 모든 것을 O(N) 시간에 전처리하여 약간의 비용을 지불합니다. 그 후, 키로 무언가를 찾는 데 평균적으로 일정한 시간이 걸립니다(이 경우 우리의 키는 그리드로 반올림된 위도 및 경도 좌표입니다. 일정한).
• 우리의 작업은 실행 불가능한 O(N²) 에서 관리 가능한 O(N) 바뀌었고 해시 테이블을 만드는 데 약간의 비용을 지불하기만 하면 됩니다.
• analogy : 이 특별한 경우의 비유는 직소 퍼즐입니다. 우리는 데이터의 일부 속성을 이용하는 데이터 구조를 만들었습니다. 도로 구간이 퍼즐 조각과 같다면 색상과 패턴을 일치시켜 그룹화합니다. 그런 다음 나중에 추가 작업을 피하기 위해 이것을 이용합니다(다른 모든 단일 퍼즐 조각이 아니라 같은 색상의 퍼즐 조각을 서로 비교).

이야기의 교훈: 데이터 구조를 통해 작업 속도를 높일 수 있습니다. 더욱이 고급 데이터 구조를 사용하면 믿을 수 없을 정도로 영리한 방식으로 작업을 결합, 지연 또는 무시할 수 있습니다. 서로 다른 문제는 서로 다른 유추를 가지지만 모두 우리가 관심 있는 일부 구조를 활용하거나 부기를 위해 인위적으로 부과한 방식으로 데이터를 구성하는 것과 관련이 있습니다. 우리는 미리 작업(기본적으로 계획 및 구성)을 수행하고 이제 반복되는 작업이 훨씬 쉬워졌습니다!

---

실제 예: 코딩하는 동안 성장 순서 시각화

점근적 표기법은 핵심적으로 프로그래밍과 완전히 별개입니다. 점근적 표기법은 사물이 어떻게 확장되고 다양한 분야에서 사용될 수 있는지 생각하기 위한 수학적 프레임워크입니다. 즉... 이것이 코딩에 점근적 표기법을 적용하는 방법입니다.

기본 사항: 크기 A 컬렉션의 모든 요소(예: 배열, 집합, 맵의 모든 키 등)와 상호 작용하거나 루프의 A 반복을 수행할 때마다 크기 A의 곱셈 요소입니다. 내가 "승법 요소"라고 말하는 이유는 무엇입니까? -- 왜냐하면 루프와 함수(거의 정의상)에는 곱셈 실행 시간이 있기 때문입니다. 함수, 함수에서 수행된 작업 시간). (이는 루프를 건너뛰거나 루프를 일찍 종료하거나 인수를 기반으로 함수의 제어 흐름을 변경하는 것과 같은 멋진 작업을 수행하지 않는 경우에도 적용됩니다. 이는 매우 일반적입니다.) 다음은 의사 코드와 함께 시각화 기술의 몇 가지 예입니다.

(여기서 x s는 일정 시간 작업 단위, 프로세서 명령, 인터프리터 opcode 등을 나타냄)

 for(i=0; i<A; i++) // A * ... some O(1) operation // 1 --> A*1 --> O(A) time visualization: |<------ A ------->| 1 2 3 4 5 xx ... x other languages, multiplying orders of growth: javascript, O(A) time and space someListOfSizeA.map((x,i) => [x,i]) python, O(rows*cols) time and space [[r*c for c in range(cols)] for r in range(rows)]

예 2:

 for every x in listOfSizeA: // A * (... some O(1) operation // 1 some O(B) operation // B for every y in listOfSizeC: // C * (... some O(1) operation // 1)) --> O(A*(1 + B + C)) O(A*(B+C)) (1 is dwarfed) visualization: |<------ A ------->| 1 xxxxxx ... x 2 xxxxxx ... x ^ 3 xxxxxx ... x | 4 xxxxxx ... x | 5 xxxxxx ... x B <-- A*B xxxxxxx ... x | ................... | xxxxxxx ... xv xxxxxxx ... x ^ xxxxxxx ... x | xxxxxxx ... x | xxxxxxx ... x C <-- A*C xxxxxxx ... x | ................... | xxxxxxx ... xv

예 3:

 function nSquaredFunction(n) { total = 0 for i in 1..n: // N * for j in 1..n: // N * total += i*k // 1 return total } // O(n^2) function nCubedFunction(a) { for i in 1..n: // A * print(nSquaredFunction(a)) // A^2 } // O(a^3)

약간 복잡한 작업을 수행하더라도 계속 진행 중인 작업을 시각적으로 상상할 수 있습니다.

 for x in range(A): for y in range(1..x): simpleOperation(x*y) xxxxxxxxxx | xxxxxxxxx | xxxxxxxx | xxxxxxx | xxxxxx | xxxxx | xxxx | xxx | xx | x___________________|

여기서 가장 작은 인식 가능한 윤곽선이 중요합니다. 삼각형은 2차원 모양(0.5A^2)입니다. 정사각형이 2차원 모양(A^2)인 것과 같습니다. 여기에서 상수 2의 인수는 둘 사이의 점근적 비율에 남아 있지만 모든 요소와 마찬가지로 무시합니다... (이 기술에 대한 몇 가지 불행한 뉘앙스가 있습니다. 여기에서 다루지 않습니다. 이는 당신을 오도할 수 있습니다.)

물론 이것이 루프와 함수가 나쁘다는 것을 의미하지는 않습니다. 반대로, 그것들은 현대 프로그래밍 언어의 빌딩 블록이며 우리는 그것들을 사랑합니다. 그러나 루프, 함수 및 조건문을 데이터(제어 흐름 등)와 함께 짜는 방식이 프로그램의 시간 및 공간 사용을 모방한다는 것을 알 수 있습니다! 시간과 공간의 사용이 문제가 되면 영리함에 의지하고 우리가 생각하지 못한 쉬운 알고리즘이나 데이터 구조를 찾아 어떻게든 성장의 순서를 줄이는 것입니다. 그럼에도 불구하고 이러한 시각화 기술(항상 작동하는 것은 아니지만)은 최악의 실행 시간에서 순진한 추측을 제공할 수 있습니다.

시각적으로 인식할 수 있는 또 다른 사항은 다음과 같습니다.

 <----------------------------- N -----------------------------> xxxxxxxxxxxxxxxxxxxxx xxxxxxxxxxx xxxxxxxxxxxxxxxx xxxxxxxx xxxx xx x

이것을 재정렬하면 O(N)임을 알 수 있습니다.

 <----------------------------- N -----------------------------> xxxxxxxxxxxxxxxxxxxxx xxxxxxxxxxx xxxxxxxxxxxxxxxx|xxxxxxxx|xxxx|xx|x

또는 O(N*log(N)) 총 시간 동안 데이터의 log(N) 전달을 수행할 수도 있습니다.

 <----------------------------- N -----------------------------> ^ xxxxxxxxxxxxxxxx|xxxxxxxxxxxxxxxx | xxxxxxxx|xxxxxxxx|xxxxxxxx|xxxxxxxx lgN xxxx|xxxx|xxxx|xxxx|xxxx|xxxx|xxxx|xxxx | xx|xx|xx|xx|xx|xx|xx|xx|xx|xx|xx|xx|xx|xx|xx|xx vx|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x

관련이 없지만 다시 언급할 가치가 있습니다. 해시(예: 사전/해시 테이블 조회)를 수행하는 경우 이는 O(1)의 요소입니다. 꽤 빠릅니다.

 [myDictionary.has(x) for x in listOfSizeA] \----- O(1) ------/ --> A*1 --> O(A)

재귀 함수 또는 분할 정복 알고리즘과 같이 매우 복잡한 작업을 수행 하는 경우 Master Theorem (일반적으로 작동함)을 사용할 수 있으며, 터무니 없는 경우 Akra-Bazzi Theorem(거의 항상 작동함) Wikipedia에서 알고리즘의 실행 시간.

그러나 프로그래머는 그렇게 생각하지 않습니다. 결국 알고리즘 직관은 제2의 천성이 되기 때문입니다. 비효율적인 코드를 작성하기 시작하면 즉시 "내가 엄청나게 비효율적인 일을 하고 있는 걸까?"라고 생각할 것입니다. 대답이 "예"이고 실제로 중요하다고 생각한다면 한 걸음 물러서서 작업을 더 빠르게 실행할 수 있는 다양한 트릭을 생각할 수 있습니다. 그리고 아주 드물게 조금 더 복잡한 것).

---

상각 및 평균 케이스 복잡성

"상각" 및/또는 "평균 사례"의 개념도 있습니다(이는 서로 다릅니다).

Average Case : 함수 자체가 아니라 함수의 기대값에 대해 big-O 표기법을 사용하는 것에 불과합니다. 모든 입력이 동일할 가능성이 있다고 생각하는 일반적인 경우 평균 사례는 실행 시간의 평균일 뿐입니다. 예를 들어 퀵소트를 사용하면 최악의 경우가 일부 정말 나쁜 입력에 대해 O(N^2) O(N log(N)) (정말 나쁜 입력은 수가 매우 적으므로 우리가 평균적인 경우에 그것들을 알아차리지 못하는 소수).

Amortized Worst-Case : 일부 데이터 구조는 최악의 경우 복잡성이 클 수 있지만 이러한 작업을 많이 수행하면 평균 작업량이 최악의 경우보다 나을 것입니다. O(1) 시간이 걸리는 데이터 구조가 있을 수 있습니다. 그러나 때때로 부기나 가비지 수집 등을 수행해야 할 수도 있기 때문에 한 번의 임의 작업에 '딸꾹질'하고 O(N) N 더 많은 작업에 대해 다시 딸꾹질. 최악의 경우 비용은 여전히 O(N) 이지만 많은 실행에 대한 분할 상환 비용은 작업당 O(N)/N = O(1) 입니다. 큰 작업은 충분히 드물기 때문에 엄청난 양의 비정기 작업이 나머지 작업과 일정한 요소로 혼합되는 것으로 간주될 수 있습니다. 우리는 작업이 점근적으로 사라지는 충분히 많은 호출에 대해 "상각"되었다고 말합니다.

상각 분석에 대한 비유:

당신은 차를 운전합니다. 가끔 10분 동안 주유소에 갔다가 1분 동안 탱크에 가스를 채워야 합니다. 당신이 당신의 차를 가지고 어디든 갈 때마다 이것을 한다면(주유소까지 차로 10분을 보내고, 몇 초를 갤런의 일부를 채우는 데 소비), 그것은 매우 비효율적일 것입니다. 그러나 며칠에 한 번씩 탱크를 채우면 주유소까지 운전하는 데 소요된 11분이 충분히 많은 여행에 걸쳐 "상각"되어 무시하고 모든 여행이 5% 더 길다고 가장할 수 있습니다.

평균 및 상각 최악의 경우 비교:

• Average-case: 우리는 입력에 대해 몇 가지 가정을 합니다. 즉, 입력에 다른 확률이 있으면 출력/런타임에 다른 확률이 있습니다(평균을 취함). 일반적으로 입력이 모두 동일할 가능성(균일한 확률)이라고 가정하지만 실제 입력이 "평균 입력"이라는 가정에 맞지 않으면 평균 출력/런타임 계산이 의미가 없을 수 있습니다. 그러나 균일하게 임의의 입력이 예상되는 경우 생각해 보면 유용합니다!
• Amortized Worst-Case: Amortized Worst-Case 데이터 구조를 사용하면 성능이 Amortized Worst-Case 이내로 보장됩니다... 결국(모든 것을 알고 있고 당신을 망쳐). 일반적으로 예상치 못한 큰 문제가 있는 성능이 매우 ' 고르지 못한' 알고리즘을 분석하는 데 이 알고리즘을 사용하지만 시간이 지남에 따라 다른 알고리즘과 동일한 성능을 발휘합니다. (그러나 데이터 구조가 기꺼이 미루고자 하는 많은 뛰어난 작업에 대한 상한선이 없는 한, 악의적인 공격자가 미루는 작업의 최대량을 한 번에 따라잡도록 강요할 수 있습니다.

하지만 공격자에 대해 합리적으로 걱정 하는 경우 분할 상환 및 평균 사례 외에도 걱정해야 할 다른 알고리즘 공격 벡터가 많이 있습니다.)

평균 사례와 상각은 모두 확장을 염두에 두고 생각하고 설계하는 데 매우 유용한 도구입니다.

(이 하위 주제에 관심이 있는 경우 평균 사례와 상각 분석의 차이점을 참조하십시오.)

---

다차원 빅오

대부분의 경우 사람들은 직장에 하나 이상의 변수가 있다는 것을 깨닫지 못합니다. 예를 들어, 문자열 검색 알고리즘에서 알고리즘은 O([length of text] + [length of query]) O(N+M) 과 같은 두 변수에서 선형입니다. 다른 순진한 알고리즘은 O([length of text]*[length of query]) 또는 O(N*M) 있습니다. 여러 변수를 무시하는 것은 알고리즘 분석에서 가장 흔히 볼 수 있는 실수 중 하나이며 알고리즘을 설계할 때 방해가 될 수 있습니다.

---

전체 이야기

Big-O가 전체 이야기가 아님을 명심하십시오. 캐싱을 사용하여 일부 알고리즘의 속도를 크게 높일 수 있고, 캐시를 인식하지 못하게 하고, 디스크 대신 RAM으로 작업하거나, 병렬 처리를 사용하거나, 미리 작업을 수행하여 병목 현상을 방지할 수 있습니다. 이러한 기술은 종종 성장 순서와 무관합니다. 병렬 알고리즘의 big-O 표기법에서 코어 수를 자주 볼 수 있지만 "big-O" 표기법입니다.

또한 프로그램의 숨겨진 제약 조건으로 인해 점근적 동작에 대해 별로 신경 쓰지 않을 수도 있다는 점을 염두에 두십시오. 다음과 같이 제한된 수의 값으로 작업할 수 있습니다.

• 5개의 요소를 정렬하는 경우 빠른 O(N log(N)) 퀵 정렬을 사용하고 싶지 않습니다. 작은 입력에서 잘 수행되는 삽입 정렬을 사용하려고 합니다. 이러한 상황은 재귀 정렬, 고속 푸리에 변환 또는 행렬 곱셈과 같이 문제를 점점 더 작은 하위 문제로 분할하는 분할 정복 알고리즘에서 자주 발생합니다.
• 숨겨진 사실로 인해 일부 값이 효과적으로 제한되는 경우(예: 평균적인 사람의 이름은 약 40자로 부드럽게 제한되고 사람의 나이는 약 150에서 부드럽게 제한됨). 또한 항을 효과적으로 일정하게 만들기 위해 입력에 경계를 부과할 수 있습니다.

심지어 동일하거나 유사한 점근 적 성능이 알고리즘 중 연습에서 상대적인 장점은 실제로 다른 같은 것들에 의해 구동 될 수있다 : 다른 성능 요인 (퀵와 머지 소트는 모두 O(N log(N)) 하지만, 퀵 소요 CPU 캐시의 장점); 구현 용이성과 같은 비 성능 고려 사항; 도서관이 이용 가능한지 여부, 도서관이 얼마나 평판이 좋고 유지 관리되는지.

프로그램은 또한 500MHz 컴퓨터와 2GHz 컴퓨터에서 더 느리게 실행됩니다. 실제 초 단위가 아니라 기계 자원(예: 클럭 주기당) 측면에서 스케일링을 생각하기 때문에 이를 리소스 경계의 일부로 고려하지 않습니다. 그러나 에뮬레이션에서 실행 중인지 또는 컴파일러가 코드를 최적화했는지 여부와 같이 성능에 '은밀히' 영향을 줄 수 있는 유사한 것들이 있습니다. 이로 인해 일부 기본 작업이 더 오래 걸리거나(서로에 대해 상대적으로) 더 오래 걸리거나 일부 작업의 속도를 점근적으로(서로에 대해) 높일 수도 있습니다. 다른 구현 및/또는 환경 간에 효과가 작거나 클 수 있습니다. 약간의 추가 작업을 수행하기 위해 언어나 기계를 바꾸십니까? 이는 성능보다 더 중요할 수 있는 수백 가지 다른 이유(필요성, 기술, 동료, 프로그래머 생산성, 시간의 금전적 가치, 친숙함, 해결 방법, 어셈블리 또는 GPU가 아닌 이유 등)에 따라 달라집니다.

사용되는 프로그래밍 언어 선택의 영향과 같은 위의 문제는 거의 상수 요소의 일부로 간주되지 않습니다. 그러나 때때로 (드물게) 영향을 미칠 수 있기 때문에 그것들을 알고 있어야 합니다. 예를 들어 cpython에서 기본 우선 순위 대기열 구현은 점근적으로 최적이 아닙니다(삽입 또는 find-min 선택에 대해 O(1) O(log(N)) 다른 구현을 사용합니까? 아마도 C 구현이 더 빠르고 다른 유사한 문제가 있을 수 있기 때문에 그렇지 않을 것입니다. 장단점이 있습니다. 때로는 중요하고 때로는 중요하지 않습니다.

---

( 편집 : "평범한 영어" 설명은 여기서 끝.)

수학 부록

완전성을 위해 big-O 표기법의 정확한 정의는 다음과 같습니다. f(x) ∈ O(g(x)) 는 "f가 const*g에 의해 점근적으로 상한임"을 의미합니다. x의 일부 유한 값 아래의 모든 것을 무시합니다. , |f(x)| ≤ const * |g(x)| . (다른 기호는 다음과 같습니다. O ≤을 의미하고 Ω ≥를 의미하는 것처럼 소문자 변형이 있습니다. o 는 <를 의미하고 ω 는 >를 의미합니다.) f(x) ∈ Ɵ(g(x)) 는 둘 다 f(x) ∈ O(g(x)) 및 f(x) ∈ Ω(g(x)) const1*g(x) 사이의 "대역"에 놓이도록 하는 몇 가지 상수가 있습니다. const1*g(x) 및 const2*g(x) . 이것은 당신이 만들 수 있는 가장 강력한 점근적 문장이며 == 와 대략 동등합니다. (죄송합니다. 명확성을 위해 절대값 기호에 대한 언급을 지금까지 연기하기로 결정했습니다. 특히 컴퓨터 과학 맥락에서 음수 값이 나오는 것을 본 적이 없기 때문입니다.)

사람들은 종종 = O(...) . 이는 아마도 더 정확한 'comp-sci' 표기법이며 사용하기에 완전히 합법입니다. "f = O(...)"는 "f is order ... / f is xxx-bounded by ..."로 읽히고 "f는 점근법이 ...인 일부 표현식"으로 생각됩니다. ∈ O(...) 를 사용하도록 배웠습니다. ∈ 는 "~의 요소"를 의미합니다(여전히 이전과 같이 읽음). 이 특별한 경우에 O(N²) 는 { 2 N² , 3 N² , 1/2 N² , 2 N² + log(N) , - N² + N^1.9 , ...} 와 같은 요소를 포함하고 무한히 크지만 아직 세트.

O와 Ω은 대칭이 아니지만(n = O(n²), n²는 O(n)이 아님), Ɵ는 대칭이고 (이러한 관계는 모두 전이적이며 반사적이므로) Ɵ는 대칭적이고 전이적이며 반사적입니다. , 따라서 모든 함수 집합을 등가 클래스 로 분할합니다. 동등 클래스는 우리가 동일하다고 생각하는 것들의 집합입니다. 즉, 생각할 수 있는 기능이 주어지면 해당 클래스의 표준/고유한 '점근적 대표자'를 찾을 수 있습니다(일반적으로 제한을 취함으로써... 제 생각에는 ). 모든 정수를 홀수 또는 짝수로 그룹화할 수 있는 것처럼 기본적으로 더 작은 용어를 무시하여 Ɵ가 있는 모든 함수를 x-ish, log(x)^2-ish 등으로 그룹화할 수 있습니다(그러나 때로는 자체적으로 클래스를 분리하는 더 복잡한 기능).

= 표기법이 더 일반적일 수 있으며 세계적으로 유명한 컴퓨터 과학자의 논문에서도 사용됩니다. 또한 캐주얼한 상황에서 사람들은 Ɵ(...) 의미할 때 O(...) 라고 말하는 경우가 많습니다. Ɵ(exactlyThis) O(noGreaterThanThis) ...의 하위 집합이기 때문에 기술적으로 사실이며 입력하기가 더 쉽습니다. ;-)

답변자 : Jon Skeet

편집: 빠른 메모, 이것은 Big O 표기법 (상한선)과 Theta 표기법(상한선 및 하한선 모두)을 거의 확실히 혼동합니다. 내 경험에 따르면 이것은 실제로 비학문적 환경에서의 토론의 전형입니다. 혼란을 드려 죄송합니다.

한 문장으로: 작업의 규모가 커질수록 완료하는 데 얼마나 더 걸리나요?

분명히 그것은 "크기"를 입력으로 사용하고 "소요된 시간"을 출력으로 사용하는 것입니다. 메모리 사용 등에 대해 이야기하려는 경우에도 동일한 아이디어가 적용됩니다.

다음은 우리가 말리고 싶은 N개의 티셔츠가 있는 예입니다. 건조 위치에 두는 것이 믿을 수 없을 정도로 빠르다고 가정 하겠습니다(즉, 사람의 상호 작용은 무시할 수 있음). 물론 현실에서는 그렇지 않습니다만...

• 외부 세탁 라인 사용: 뒷마당이 무한히 크다고 가정하면 세탁은 O(1) 시간에 건조됩니다. 아무리 많이 가지고 있어도 동일한 태양과 신선한 공기를 얻을 수 있으므로 크기는 건조 시간에 영향을 미치지 않습니다.

• 회전식 건조기 사용: 각 로드에 10개의 셔츠를 넣고 한 시간 후에 완료됩니다. (여기서 실제 숫자는 무시하십시오. 관련이 없습니다.) 따라서 50개의 셔츠를 건조하는 것은 10개의 셔츠를 건조하는 것보다 약 5배의 시간이 걸립니다.

• 통풍 찬장에 모든 것을 담기: 모든 것을 하나의 큰 더미에 넣고 일반적인 따뜻함을 허용하면 중간 셔츠가 마르는 데 오랜 시간이 걸립니다. 세부 사항을 추측하고 싶지는 않지만 이것이 적어도 O(N^2)인 것으로 생각됩니다. 세탁 부하가 증가할수록 건조 시간이 더 빨리 증가합니다.

"big O" 표기법의 한 가지 중요한 측면은 주어진 크기에 대해 어떤 알고리즘이 더 빠를 지 말하지 않는다는 것입니다. 해시 테이블(문자열 키, 정수 값) 대 쌍의 배열(문자열, 정수)을 가져옵니다. 문자열을 기반으로 해시 테이블의 키 또는 배열의 요소를 찾는 것이 더 빠릅니까? (즉, 배열의 경우 "문자열 부분이 주어진 키와 일치하는 첫 번째 요소를 찾으십시오.") 해시 테이블은 일반적으로 상각됩니다(~= "평균") O(1) — 일단 설정되면 1,000,000 항목 테이블에서와 같이 100 항목 테이블에서 항목을 찾는 동시에. 배열에서 요소를 찾는 것은(인덱스가 아닌 내용을 기반으로) 선형입니다. 즉, O(N) — 평균적으로 항목의 절반을 살펴봐야 합니다.

이것은 조회를 위해 배열보다 해시 테이블을 더 빠르게 만드나요? 반드시는 아닙니다. 항목 모음이 매우 작은 경우 배열이 더 빠를 수 있습니다. 보고 있는 항목의 해시 코드를 계산하는 데 걸리는 시간에 모든 문자열을 확인할 수 있습니다. 그러나 데이터 세트가 커질수록 해시 테이블은 결국 배열을 능가합니다.

답변자 : starblue

Big O는 입력이 커질 때 프로그램의 런타임과 같은 기능의 성장 동작에 대한 상한을 설명합니다.

예:

• O(n): 입력 크기를 두 배로 늘리면 런타임이 두 배가 됩니다.

• O(n ² ): 입력 크기가 런타임을 4배로 하는 경우

• O(log n): 입력 크기가 2배이면 런타임이 1 증가합니다.

• O(2 ⁿ ): 입력 크기가 1 증가하면 런타임이 두 배가 됩니다.

입력 크기는 일반적으로 입력을 나타내는 데 필요한 비트 단위의 공간입니다.

답변자 : cdiggins

Big O 표기법은 입력 세트 크기의 함수로 표현되는 계산(알고리즘)이 완료되는 데 걸리는 대략적인 측정으로 프로그래머가 가장 일반적으로 사용합니다.

Big O는 입력 수가 증가함에 따라 두 알고리즘이 얼마나 잘 확장되는지 비교하는 데 유용합니다.

보다 정확하게는 Big O 표기법 이 함수의 점근적 동작을 표현하는 데 사용됩니다. 이는 함수가 무한대에 접근할 때 어떻게 동작하는지를 의미합니다.

많은 경우 알고리즘의 "O"는 다음 경우 중 하나에 해당합니다.

• O(1) - 입력 집합의 크기에 관계없이 완료하는 데 걸리는 시간은 동일합니다. 예는 인덱스로 배열 요소에 액세스하는 것입니다.
• O(Log N) - 완료 시간은 대략 log2(n)에 따라 증가합니다. 예를 들어 Log2(1024) = 10이고 Log2(32) = 5이기 때문에 1024개 항목은 32개 항목보다 대략 두 배 정도 더 오래 걸립니다. 예를 들어 이진 검색 트리 (BST)에서 항목을 찾는 것이 있습니다.
• O(N) - 입력 세트의 크기에 따라 선형으로 확장되는 완료 시간입니다. 다시 말해, 입력 세트의 항목 수를 두 배로 늘리면 알고리즘에 약 두 배의 시간이 걸립니다. 예는 연결 목록의 항목 수를 계산하는 것입니다.
• O(N Log N) - 완료 시간은 Log2(N)의 결과에 항목 수를 곱한 만큼 증가합니다. 예를 들어 힙 정렬 과 빠른 정렬이 있습니다.
• O(N^2) - 완료하는 데 걸리는 시간은 항목 수의 제곱과 거의 같습니다. 이것의 예는 버블 정렬 입니다.
• O(N!) - 완료 시간은 입력 세트의 계승입니다. 이에 대한 예는 순회 판매원 문제 무차별 대입 솔루션 입니다.

Big O는 입력 크기가 무한대로 증가함에 따라 함수의 성장 곡선에 의미 있는 방식으로 기여하지 않는 요인을 무시합니다. 즉, 함수에 더하거나 곱한 상수는 단순히 무시됩니다.

답변자 : Filip Ekberg

Big O는 "내 코드를 실행하는 데 얼마나 많은 시간/공간이 필요합니까?"라는 일반적인 방식으로 자신을 "표현"하는 방법입니다.

종종 O(n), O(n ² ), O(nlogn) 등을 볼 수 있습니다. 알고리즘은 어떻게 변경됩니까?

O(n)은 Big O가 n임을 의미하며 이제 "n이 무엇입니까!?"라고 생각할 수 있습니다. 음 "n"은 요소의 양입니다. 배열에서 항목을 검색하려는 이미징. 각 요소를 보고 "올바른 요소/항목입니까?"로 확인해야 합니다. 최악의 경우 항목이 마지막 인덱스에 있으므로 목록에 있는 항목만큼 시간이 걸리므로 일반적으로 "오, n은 주어진 값의 공정한 양입니다!"라고 말합니다. .

그러면 "n ² "가 무엇을 의미하는지 이해할 수 있지만 더 구체적으로 말하면 정렬 알고리즘 중 가장 단순하고 단순한 것이 있다고 생각하고 플레이하십시오. 버블정렬. 이 알고리즘은 각 항목에 대해 전체 목록을 살펴봐야 합니다.

나의 목록

1. 1
2. 6
3. 삼

여기서의 흐름은 다음과 같습니다.

• 1과 6을 비교하여 어느 것이 가장 큰가? Ok 6이 올바른 위치에 있습니다. 앞으로 나아가십시오!
• 6과 3을 비교하면 오, 3은 더 적습니다! 이동합시다. 목록이 변경되었습니다. 이제 처음부터 시작해야 합니다!

이것은 "n"개의 항목이 있는 목록의 모든 항목을 살펴봐야 하기 때문에 O n ^2입니다. 각 항목에 대해 모든 항목을 한 번 더 확인합니다. 비교를 위해 이것도 "n"이므로 모든 항목에 대해 n*n = n ^{2를 의미하는 "n"번을 봅니다.}

이것이 원하는 만큼 간단하기를 바랍니다.

그러나 Big O는 시간과 공간의 방식으로 자신을 표현하는 방법일 뿐입니다.

답변자 : Wedge

Big O는 알고리즘의 기본적인 확장성을 설명합니다.

Big O가 주어진 알고리즘에 대해 알려주지 않는 정보가 많이 있습니다. 뼈대를 자르고 알고리즘의 크기 조정 특성, 특히 "입력 크기"에 대한 응답으로 알고리즘의 리소스 사용(생각 시간 또는 메모리)이 조정되는 방식에 대한 정보만 제공합니다.

증기 기관과 로켓의 차이점을 고려하십시오. 그것들은 단지 같은 것의 다른 종류(예: Prius 엔진 대 Lamborghini 엔진)가 아니라 그 핵심에서 극적으로 다른 종류의 추진 시스템입니다. 증기 기관은 장난감 로켓보다 빠를 수 있지만 증기 피스톤 엔진은 궤도 발사체의 속도를 달성할 수 없습니다. 이는 이러한 시스템이 주어진 속도("입력 크기")에 도달하는 데 필요한 연료("자원 사용")의 관계와 관련하여 다른 크기 조정 특성을 가지고 있기 때문입니다.

이것이 왜 그렇게 중요한가? 소프트웨어는 최대 1조 개의 요인에 의해 크기가 다를 수 있는 문제를 처리하기 때문입니다. 잠시 생각해보십시오. 달을 여행하는 데 필요한 속도와 사람이 걷는 속도 사이의 비율은 10,000:1 미만이며 소프트웨어가 직면할 수 있는 입력 크기의 범위에 비해 절대적으로 작습니다. 그리고 소프트웨어는 입력 크기의 천문학적 범위에 직면할 수 있기 때문에 알고리즘의 Big O 복잡성이 발생할 가능성이 있으므로 구현 세부 사항을 능가하는 것이 기본적인 확장 특성입니다.

표준 정렬 예제를 고려하십시오. 버블 정렬은 O(n ² )이고 병합 정렬은 O(n log n)입니다. 버블 정렬을 사용하는 애플리케이션 A와 병합 정렬을 사용하는 애플리케이션 B의 두 가지 정렬 응용 프로그램이 있다고 가정하고 약 30개 요소의 입력 크기에 대해 응용 프로그램 A는 정렬 시 응용 프로그램 B보다 1,000배 더 빠릅니다. 30개 이상의 요소를 정렬할 필요가 없다면 이러한 입력 크기에서 훨씬 빠르기 때문에 애플리케이션 A를 선호해야 한다는 것이 분명합니다. 그러나 천만 개의 항목을 정렬해야 할 수도 있다는 사실을 알게 된다면 애플리케이션 B가 실제로 이 경우 애플리케이션 A보다 수천 배 더 빠를 것으로 예상할 수 있습니다. 이는 전적으로 각 알고리즘의 확장 방식 때문입니다.

답변자 : Andrew Prock

다음은 Big-O의 일반적인 품종을 설명할 때 사용하는 평범한 영어 동물입니다.

모든 경우에, 목록에서 낮은 것보다 높은 것보다 높은 것의 알고리즘을 선호하십시오. 그러나 더 비싼 복잡성 클래스로 이동하는 비용은 크게 다릅니다.

오(1):

성장이 없습니다. 문제가 아무리 크더라도 같은 시간에 풀 수 있습니다. 이는 방송 범위 내에 있는 사람의 수에 관계없이 주어진 거리에서 방송하는 데 동일한 양의 에너지가 소요되는 방송과 다소 유사합니다.

O(로그 n ):

이 복잡성은 조금 더 나쁘다는 점을 제외하고는 O(1)과 동일합니다. 모든 실용적인 목적을 위해 이것을 매우 큰 일정한 스케일링으로 간주할 수 있습니다. 1000억 항목과 10억 항목 처리 간의 작업 차이는 6배에 불과합니다.

오( n ):

문제 해결 비용은 문제의 크기에 비례합니다. 문제의 크기가 두 배가 되면 솔루션 비용도 두 배가 됩니다. 대부분의 문제는 데이터 입력, 디스크 읽기 또는 네트워크 트래픽과 같은 어떤 방식으로든 컴퓨터로 스캔해야 하기 때문에 일반적으로 합리적인 확장 요소입니다.

O( n 로그 n ):

이 복잡성은 O( n ) 과 매우 유사합니다. 모든 실용적인 목적을 위해 둘은 동일합니다. 이 수준의 복잡성은 일반적으로 여전히 확장 가능한 것으로 간주됩니다. 가정을 조정하여 일부 O( n log n ) 알고리즘을 O( n ) 알고리즘으로 변환할 수 있습니다. 예를 들어, 키 크기를 제한하면 O( n log n ) 에서 O( n ) 으로의 정렬이 줄어듭니다.

O (N ²⁾

정사각형으로 자랍니다. 여기서 n 은 정사각형의 한 변의 길이입니다. 이것은 네트워크의 모든 사람이 네트워크의 다른 모든 사람을 알 수 있는 "네트워크 효과"와 동일한 성장률입니다. 성장은 비용이 많이 듭니다. 대부분의 확장 가능한 솔루션은 상당한 체조 없이는 이러한 수준의 복잡성을 가진 알고리즘을 사용할 수 없습니다. 이것은 일반적으로 다른 모든 다항식 복잡성 (O( n ^k )) 에도 적용됩니다.

O( ²ⁿ ):

확장하지 않습니다. 사소하지 않은 크기의 문제를 해결할 희망은 없습니다. 피해야 할 사항을 알고 전문가가 O( n ^k ) 에 있는 대략적인 알고리즘을 찾는 데 유용합니다.

답변자 : Brownie

Big O는 입력 크기에 비해 알고리즘이 사용하는 시간/공간의 측정값입니다.

알고리즘이 O(n)이면 시간/공간은 입력과 동일한 비율로 증가합니다.

알고리즘이 O(n ² )이면 시간/공간은 입력 제곱의 비율로 증가합니다.

등등.

답변자 : William Payne

소프트웨어 프로그램의 속도를 측정하는 것은 매우 어렵습니다. 우리가 시도할 때 응답은 매우 복잡하고 예외와 특수한 경우로 가득 차 있을 수 있습니다. 이것은 큰 문제입니다. 왜냐하면 우리가 "가장 빠른" 프로그램을 찾기 위해 두 개의 다른 프로그램을 서로 비교하려고 할 때 이러한 모든 예외와 특별한 경우는 주의를 산만하게 하고 도움이 되지 않기 때문입니다.

이 모든 도움이 되지 않는 복잡성의 결과로 사람들은 가능한 가장 작고 가장 덜 복잡한(수학적) 표현을 사용하여 소프트웨어 프로그램의 속도를 설명하려고 합니다. 이 표현은 매우 조잡한 근사치입니다. 약간의 운이 좋으면 소프트웨어가 빠른지 느린지의 "본질"을 포착할 수 있습니다.

그것들은 근사치이기 때문에 우리가 지나치게 단순화하고 있다는 것을 독자에게 알리는 관례로 표현에서 문자 "O"(Big Oh)를 사용합니다. (그리고 아무도 그 표현이 어떤 식으로든 정확하다고 잘못 생각하지 않도록 하기 위해).

"오"를 "순서대로" 또는 "대략"을 의미하는 것으로 읽으면 크게 잘못되지는 않을 것입니다. (Big-Oh의 선택은 유머를 시도한 것일 수도 있다고 생각합니다.)

이러한 "Big-Oh" 표현이 하려고 하는 유일한 것은 소프트웨어가 처리해야 하는 데이터의 양이 증가함에 따라 소프트웨어가 얼마나 느려지는지를 설명하는 것입니다. 처리해야 하는 데이터의 양을 두 배로 늘리면 소프트웨어가 작업을 완료하는 데 두 배의 시간이 필요합니까? 열배? 실제로 마주하고 걱정해야 하는 big-Oh 표현의 수는 매우 제한적입니다.

좋은:

• O(1) 상수 : 입력이 아무리 많아도 프로그램이 실행되는 데 걸리는 시간은 같습니다.
• O(log n) 대수 : 입력 크기가 크게 증가하더라도 프로그램 실행 시간은 천천히 증가합니다.

나쁜:

• O(n) Linear : 프로그램 실행 시간이 입력 크기에 비례하여 증가합니다.
• O(n^k) 다항식 : - 처리 시간은 입력의 크기가 증가함에 따라 - 다항식 함수로서 - 점점 더 빨라집니다.

... 그리고 못생긴:

• O(k^n) 지수 프로그램 실행 시간은 문제의 크기가 약간 증가하더라도 매우 빠르게 증가합니다. 지수 알고리즘을 사용하여 작은 데이터 세트를 처리하는 것이 실용적입니다.
• O(n!) 팩토리얼 프로그램 실행 시간은 가장 작고 가장 사소해 보이는 데이터 세트를 제외하고는 기다릴 여유가 있는 것보다 더 깁니다.

답변자 : James Oravec

Big O에 대한 쉬운 영어 설명은 무엇입니까? 가능한 한 적은 형식적 정의와 간단한 수학으로.

Big-O 표기법 의 필요성에 대한 간단한 영어 설명:

프로그래밍할 때 문제를 해결하려고 합니다. 우리가 코딩하는 것을 알고리즘이라고 합니다. Big O 표기법을 사용하면 알고리즘의 더 나쁜 경우의 성능을 표준화된 방식으로 비교할 수 있습니다. 하드웨어 사양은 시간이 지남에 따라 달라지며 하드웨어의 개선으로 알고리즘을 실행하는 데 걸리는 시간을 줄일 수 있습니다. 그러나 하드웨어를 교체한다고 해서 알고리즘이 여전히 동일하기 때문에 시간이 지남에 따라 알고리즘이 더 좋아지거나 개선되는 것은 아닙니다. 따라서 다른 알고리즘을 비교할 수 있도록 하기 위해 하나가 더 나은지 여부를 결정하기 위해 Big O 표기법을 사용합니다.

Big O 표기법이 무엇인지에 대한 간단한 영어 설명:

모든 알고리즘이 동일한 시간에 실행되는 것은 아니며 입력의 항목 수에 따라 달라질 수 있습니다. 이를 n 이라고 합니다. 이를 기반으로 n 이 커질수록 더 나쁜 경우 또는 런타임의 상한을 고려합니다. 많은 Big O 표기법이 n을 참조하기 때문에 n이 무엇인지 알고 있어야 합니다.

답변자 : Ajeet Ganga

좋아, 내 2센트.

Big-O는 문제 인스턴스 크기를 나타내는 프로그램이 소비하는 리소스 의 증가율입니다.

리소스: 총 CPU 시간이 될 수 있으며 최대 RAM 공간이 될 수 있습니다. 기본적으로 CPU 시간을 나타냅니다.

문제가 "합계 찾기"라고 가정하고,

 int Sum(int*arr,int size){ int sum=0; while(size-->0) sum+=arr[size]; return sum; }

문제 인스턴스 = {5,10,15} ==> 문제 인스턴스 크기 = 3, 루프 내 반복 = 3

문제 인스턴스 = {5,10,15,20,25} ==> 문제 인스턴스 크기 = 5 루프 내 반복 = 5

크기 "n"의 입력에 대해 프로그램은 배열에서 "n" 반복의 속도로 성장합니다. 따라서 Big-O는 O(n)으로 표현되는 N입니다.

문제가 "조합 찾기"라고 가정하고,

 void Combination(int*arr,int size) { int outer=size,inner=size; while(outer -->0) { inner=size; while(inner -->0) cout<<arr[outer]<<"-"<<arr[inner]<<endl; } }

문제 인스턴스 = {5,10,15} ==> 문제 인스턴스 크기 = 3, 총 반복 횟수 = 3*3 = 9

문제 인스턴스= {5,10,15,20,25} ==> 문제 인스턴스 크기 = 5, 총 반복 횟수= 5*5 =25

크기 "n"의 입력에 대해 프로그램은 배열에서 "n*n" 반복의 속도로 성장합니다. 따라서 Big-O는 O(n ² ) ^{로 표현되는 N 2 입니다.}

답변자 : AlienOnEarth

간단하고 간단한 대답은 다음과 같습니다.

Big O는 해당 알고리즘에 대해 가능한 최악의 시간/공간을 나타냅니다. 알고리즘은 해당 제한보다 많은 공간/시간을 차지하지 않습니다. Big O는 극단적인 경우 시간/공간 복잡성을 나타냅니다.

답변자 : John C Earls

Big O 표기법은 공간 또는 실행 시간 측면에서 알고리즘의 상한을 설명하는 방법입니다. n은 문제의 요소 수(즉, 배열의 크기, 트리의 노드 수 등)입니다. n이 커질수록 실행 시간을 설명하는 데 관심이 있습니다.

어떤 알고리즘이 O(f(n))라고 말할 때 우리는 그 알고리즘에 의해 실행되는 시간(또는 필요한 공간)이 항상 일정한 시간 f(n)보다 낮다는 것을 의미합니다.

이진 검색의 실행 시간이 O(logn)이라는 것은 log(n)을 곱할 수 있는 상수 c가 있으며 항상 이진 검색의 실행 시간보다 크다는 것을 의미합니다. 이 경우 항상 log(n) 비교의 일정한 요소를 갖게 됩니다.

즉, g(n)이 알고리즘의 실행 시간인 경우 g(n) <= c*f(n)일 때 g(n) = O(f(n))라고 합니다. c와 k는 일부 상수입니다.

답변자 : Joseph Myers

" Big O에 대한 평범한 영어 설명은 무엇입니까? 가능한 한 적은 형식 정의와 간단한 수학으로. "

이처럼 아름답고 단순하고 짧은 질문은 학생이 과외를 하는 동안 받을 수 있는 것처럼 최소한 똑같이 짧은 답변을 받을 자격이 있는 것 같습니다.

Big O 표기법은 단순히 입력 데이터 ** 의 양으로 알고리즘이 얼마나 많은 시간* 내에서 실행될 수 있는지 알려줍니다.

( * 단위가 없는 멋진 시간 감각으로!)
(**이것이 중요합니다. 왜냐하면 사람들은 오늘을 살든 내일을 살든 항상 더 많은 것을 원할 것이기 때문입니다.)

글쎄요, Big O 표기법이 그것이 하는 일이라면 무엇이 그렇게 멋진가요?

• 빅 O는 알고리즘 자체의 복잡성에 정면 초점을두고 완전히 단순히 비례 상수와 같은 자바 스크립트 엔진, CPU의 속도, 인터넷 연결, 그리고 아무것도를 무시하기 때문에 실질적으로 말하기, 빅 O 분석은 매우 유용하고 중요하다 빠르게 변해가는 모든 것들은 Model T 처럼 웃기게도 구식이 됩니다. Big O는 현재 또는 미래를 사는 사람들에게 동등하게 중요한 방식으로만 성과에 중점을 둡니다.

• Big O 표기법은 또한 컴퓨터 프로그래밍/엔지니어링의 가장 중요한 원리, 즉 모든 훌륭한 프로그래머가 계속 생각하고 꿈꾸도록 고무하는 사실에 직접적으로 스포트라이트를 비춥니다. 기술의 느린 진보를 넘어 결과를 달성하는 유일한 방법 은 더 나은 것을 발명하는 것입니다 알고리즘 .

답변자 : Khaled.K

알고리즘 예(자바):

 public boolean search(/* for */Integer K,/* in */List</* of */Integer> L) { for(/* each */Integer i:/* in */L) { if(i == K) { return true; } } return false; }

알고리즘 설명:

• 이 알고리즘은 목록을 항목별로 검색하고 키를 찾고,

• 목록의 각 항목을 반복하면서 그것이 키라면 True를 반환하고,

• 키를 찾지 않고 루프가 완료되면 False를 반환합니다.

Big-O 표기법은 복잡성(시간, 공간, ..)의 상한을 나타냅니다.

시간 복잡도에 대한 Big-O를 찾으려면 다음을 수행하십시오.

• 최악의 경우 시간(입력 크기 관련)을 계산합니다.

• 최악의 경우: 키가 목록에 존재하지 않습니다.

• 시간(최악의 경우) = 4n+1

• 시간: O(4n+1) = O(n) | Big-O에서는 상수가 무시됩니다.

• O(n) ~ 선형

Best-Case의 복잡성을 나타내는 Big-Omega도 있습니다.

• 최상의 경우: 키는 첫 번째 항목입니다.

• 시간(최상의 경우) = 4

• 시간: Ω(4) = O(1) ~ Instant\Constant

답변자 : Alexey

빅오

f (x) = O( g (x)) x가 a로 갈 때(예: a = +∞) 다음과 같은 함수 k가 있음을 의미합니다.

1. f (x) = k (x) g (x)

2. k는 (a = +∞인 경우 x > N, | k (x)| < M에 대해 숫자 N과 M이 있음을 의미합니다.)

다시 말해서, 일반 영어에서 f (x) = O( g (x)), x → a는 a의 이웃에서 f 가 g 와 일부 유계 함수의 곱으로 분해된다는 것을 의미합니다.

작은 오

그건 그렇고, 여기 작은 o의 정의를 비교하기 위해 있습니다.

f (x) = o( g (x)) x가 다음과 같은 함수 k가 있음을 의미합니다.

1. f (x) = k (x) g (x)

2. k (x)는 x가 a로 갈 때 0이 됩니다.

예

• x → 0일 때 sin x = O(x).

• sin x = O(1) x → +∞일 때,

• x ² + x = O(x) x → 0일 때,

• x ² + x = O(x ² ) x → +∞일 때,

• x → +∞일 때 ln(x) = o(x) = O(x).

주목! 등호 "="가 있는 표기법은 "가짜 평등"을 사용합니다. o(g(x)) = O(g(x))이면 참이지만 O(g(x)) = o(g)이면 거짓입니다. (NS)). 유사하게 x → +∞일 때 "ln(x) = o(x)"라고 쓰는 것은 괜찮지만 "o(x) = ln(x)"라는 공식은 의미가 없습니다.

더 많은 예

• O(1) = O(n) = O(n ² ) n → +∞일 때 (그러나 반대의 경우가 아니라 평등은 "가짜"임),

• n → +∞일 때 O(n) + O(n ² ) = O(n ^{2 )}

• n → +∞일 때 O(O(n ² )) = O(n ^{2 )}

• n → +∞일 때 O(n ² )O(n ³ ) = O(n ^{5 )}

---

다음은 Wikipedia 기사입니다. https://en.wikipedia.org/wiki/Big_O_notation

답변자 : user2427354

Big O 표기법은 "n"이라고 하는 임의의 수의 입력 매개변수가 주어지면 알고리즘이 얼마나 빨리 실행되는지 설명하는 방법입니다. 다른 기계가 다른 속도로 작동하기 때문에 컴퓨터 과학에 유용합니다. 그리고 단순히 알고리즘에 5초가 걸린다고 말하는 것은 많은 것을 말해주지 않습니다. 왜냐하면 4.5Ghz 옥토 코어 프로세서가 있는 시스템을 실행하는 동안 나는 15년 된 800Mhz 시스템으로 알고리즘에 관계없이 더 오래 걸릴 수 있습니다. 따라서 알고리즘이 시간 측면에서 실행되는 속도를 지정하는 대신 입력 매개변수의 수 또는 "n"의 측면에서 알고리즘이 실행되는 속도를 말합니다. 이런 식으로 알고리즘을 설명하면 컴퓨터 자체의 속도를 고려하지 않고도 알고리즘의 속도를 비교할 수 있습니다.

답변자 : Priidu Neemre

주제에 더 기여하고 있는지 확실하지 않지만 여전히 공유할 생각입니다. 한 번 이 블로그 게시물 에 Big O에 대한 매우 유용한(매우 기본적인) 설명 및 예제가 있다는 것을 알았습니다.

예를 통해 이것은 내 거북이 껍질과 같은 두개골에 기본적인 기본 사항을 이해하는 데 도움이 되었기 때문에 올바른 방향으로 나아가는 데 10분이면 충분하다고 생각합니다.

답변자 : johnwbyrd

큰 O에 대해 알아야 할 모든 것을 알고 싶으십니까? 나도 그래.

그래서 빅 O에 대해 이야기하기 위해 비트가 하나뿐인 단어를 사용하겠습니다. 단어당 하나의 소리. 작은 말은 빠르다. 당신은 이 단어를 알고, 나도 마찬가지입니다. 우리는 하나의 소리로 단어를 사용할 것입니다. 그들은 작다. 나는 당신이 우리가 사용할 모든 단어를 알고있을 것이라고 확신합니다!

이제 당신과 내가 일에 대해 이야기해 봅시다. 대부분의 경우 일을 좋아하지 않습니다. 일을 좋아하세요? 당신이 하는 경우일 수도 있지만 나는 그렇지 않다고 확신합니다.

나는 일하러 가기를 좋아하지 않는다. 나는 직장에서 시간을 보내는 것을 좋아하지 않는다. 제 방식대로라면 그냥 놀고 재미있는 일을 하고 싶어요. 저와 같은 마음이신가요?

이제 가끔은 일하러 가야 합니다. 슬프지만 사실입니다. 그래서 저는 직장에 있을 때 규칙이 있습니다. 일을 덜 하려고 합니다. 내가 할 수 있는 한 거의 일이 없다. 그럼 난 놀러갈게!

그래서 여기 큰 소식이 있습니다. 큰 O는 제가 일을 하지 않도록 도와줄 수 있습니다! 큰 O를 알면 더 많이 놀 수 있습니다. 덜 일하고 더 많이 놀 수 있습니다! 그것이 큰 O가 나를 도와주는 것입니다.

이제 할 일이 있습니다. 나는 이 목록을 가지고 있다: 하나, 둘, 셋, 넷, 다섯, 여섯. 이 목록에 있는 모든 것을 추가해야 합니다.

와, 일이 싫다. 하지만 음, 나는 이것을해야합니다. 그래서 여기 내가 간다.

1 더하기 2는 3… 더하기 3은 6… 그리고 4는… 잘 모르겠습니다. 나는 길을 잃었다. 내 머리로는 너무 어렵습니다. 나는 이런 종류의 일에 별로 관심이 없다.

그러니 일을 하지 맙시다. 당신과 내가 얼마나 힘든지 생각해봅시다. 숫자 6개를 더하려면 얼마나 해야 할까요?

어디 한번 보자. 1과 2를 더한 다음 3에 더한 다음 4에 더해야 합니다... 모두 합해서 6을 더합니다. 이 문제를 해결하려면 6개의 추가 작업을 수행해야 합니다.

이 수학이 얼마나 어려운지 알려주기 위해 큰 O가 나옵니다.

Big O는 다음과 같이 말합니다. 이 문제를 해결하려면 6가지 추가 작업을 수행해야 합니다. 1에서 6까지 각 항목에 대해 하나씩 추가합니다. 6개의 작은 작업... 각 작업은 하나의 추가 작업입니다.

글쎄, 나는 지금 그들을 추가하는 작업을하지 않을 것입니다. 하지만 그것이 얼마나 힘든 일인지 알고 있습니다. 6개를 더하면 됩니다.

아뇨, 이제 할 일이 더 있습니다. 쳇. 누가 이런 걸 만드는거야?!

이제 그들은 나에게 1에서 10까지 더하라고 요청합니다! 내가 그런 짓을 왜 하겠어? 나는 6에 1을 더하고 싶지 않았다. 1에서 10까지 더하면… 글쎄요… 훨씬 더 어려울 것입니다!

얼마나 더 힘들까요? 얼마나 더 일을 해야 합니까? 더 많거나 적은 단계가 필요합니까?

글쎄, 나는 10에서 10까지 각각에 대해 하나씩 10개의 덧셈을 해야 한다고 생각합니다. 10은 6보다 많습니다. 1에서 6까지, 1에서 10까지 더하려면 그만큼 더 노력해야 할 것입니다!

지금 추가하고 싶지 않습니다. 그 정도를 더하는 것이 얼마나 어려운 일인지 생각해보고 싶습니다. 그리고 가능한 한 빨리 플레이하기를 바랍니다.

1에서 6까지 추가하는 것은 약간의 작업입니다. 그러나 1에서 10까지 더하면 더 많은 작업이 필요하다는 것을 알 수 있습니까?

Big O는 당신의 친구이자 나의 것입니다. Big O는 우리가 계획을 세울 수 있도록 우리가 해야 할 일을 생각하는 데 도움이 됩니다. 그리고 빅오와 친구가 된다면 어렵지 않은 일을 선택할 수 있도록 도와줄 수 있어요!

이제 우리는 새로운 일을 해야 합니다. 안 돼. 나는 이 일을 전혀 좋아하지 않는다.

새로운 작업은 1에서 n까지 모든 것을 추가하는 것입니다.

기다리다! n은 무엇입니까? 내가 놓쳤나요? n이 무엇인지 알려주지 않으면 어떻게 1에서 n까지 더할 수 있습니까?

글쎄, 나는 n이 무엇인지 모릅니다. 나는 말하지 않았다. 너였어? 아니요? 오 글쎄. 그래서 우리는 일을 할 수 없습니다. 아휴.

그러나 지금은 일을 하지 않겠지만 n을 알면 얼마나 어려울지 짐작할 수 있습니다. n개를 더해야겠죠? 물론이야!

이제 큰 O가 와서 이 작업이 얼마나 힘든지 알려줄 것입니다. 그는 다음과 같이 말합니다. 하나에서 N까지 모든 것을 하나씩 추가하는 것은 O(n)입니다. 이 모든 것을 더하려면 [n번 더해야 한다는 것을 알고 있습니다.][1] 큰 O입니다! 그는 우리에게 어떤 종류의 일을 하는 것이 얼마나 힘든지 알려줍니다.

나에게 Big O는 크고 느린 보스맨으로 생각합니다. 그는 일에 대해 생각하지만 실행하지 않습니다. 그는 "그 작업은 빠르다"고 말할 수 있습니다. 또는 "그 일은 너무 느리고 힘들다!"라고 말할 수도 있습니다. 그러나 그는 일을 하지 않습니다. 그는 작업을 살펴보고 시간이 얼마나 걸릴지 알려줍니다.

나는 큰 O를 많이 걱정합니다. 왜? 일하기 싫어! 일하는 것을 좋아하는 사람은 없습니다. 이것이 우리 모두가 빅 오를 사랑하는 이유입니다! 그는 우리가 얼마나 빨리 일할 수 있는지 알려줍니다. 그는 우리가 얼마나 힘든 일인지 생각하도록 도와줍니다.

어, 더 많은 작업이 필요합니다. 이제 일을 하지 맙시다. 하지만 차근차근 계획을 세워보자.

그들은 우리에게 10장의 카드 한 벌을 주었습니다. 그것들은 모두 뒤섞여 있습니다: 7, 4, 2, 6… 전혀 직선이 아닙니다. 그리고 이제... 우리의 임무는 그것들을 분류하는 것입니다.

어. 그것은 많은 작업처럼 들립니다!

이 덱을 어떻게 정렬할 수 있습니까? 난 계획을 가지고있어.

처음부터 마지막까지 데크를 통해 각 쌍의 카드를 쌍으로 살펴보겠습니다. 한 쌍의 첫 번째 카드가 크고 그 쌍의 다음 카드가 작은 경우 교환합니다. 그렇지 않으면 다음 쌍으로 이동하는 식으로 계속 진행됩니다. 그러면 곧 데크가 완성됩니다.

덱이 완성되면 묻습니다. 패스에서 카드를 교환했습니까? 그렇다면 다시 한 번, 위에서부터 해야 합니다.

언젠가는 스왑이 없을 것이며, 우리의 종류의 덱이 완성될 것입니다. 너무 많은 작업!

글쎄, 그 규칙으로 카드를 정렬하려면 얼마나 많은 작업이 필요할까요?

10장의 카드가 있습니다. 그리고 대부분의 경우 -- 즉, 운이 좋지 않다면 -- 저는 전체 덱을 최대 10번까지 거쳐야 하며, 덱을 통해 매번 최대 10개의 카드 스왑을 수행해야 합니다.

빅오, 도와주세요!

Big O가 와서 다음과 같이 말합니다. n장의 카드로 구성된 데크에 대해 이러한 방식으로 정렬하는 것은 O(N 제곱) 시간에 완료됩니다.

그는 왜 n제곱이라고 말합니까?

n 제곱은 n 곱하기 n입니다. 이제 알겠습니다. n개의 카드를 확인했습니다. 최대 n개의 카드가 데크를 통과할 수 있습니다. 각각 n 단계가 있는 두 개의 루프입니다. 그것은 n 제곱으로 해야 할 일입니다. 많은 작업, 확실히!

이제 큰 O가 O(n 제곱) 작업이 필요하다고 말할 때 코에 n 제곱 추가를 의미하지는 않습니다. 경우에 따라 조금 더 적을 수도 있습니다. 그러나 최악의 경우 데크를 분류하는 데 거의 n제곱 단계의 작업이 필요합니다.

이제 빅오가 우리의 친구가 된 곳입니다.

Big O는 다음과 같이 지적합니다. n이 커질수록 우리가 카드를 정렬할 때 이 작업은 이전의 그냥 추가 작업보다 훨씬 더 어려워집니다. 우리는 이것을 어떻게 압니까?

음, n이 정말 커지면 n 또는 n 제곱에 무엇을 더할지 신경 쓰지 않습니다.

큰 n의 경우 n의 제곱은 n보다 큽니다.

Big O는 정렬하는 것이 추가하는 것보다 어렵다고 말합니다. O(n 제곱)은 큰 n에 대해 O(n)보다 큽니다. 즉, n이 정말 커지면 n개의 혼합 데크를 정렬하는 데 n개의 혼합 항목을 추가하는 것보다 더 많은 시간이 필요합니다.

Big O는 우리를 위해 일을 해결하지 않습니다. Big O는 작업이 얼마나 힘든지 알려줍니다.

카드 한 벌이 있습니다. 나는 그들을 정렬했다. 당신이 도왔습니다. 감사 해요.

카드를 정렬하는 더 빠른 방법이 있습니까? 큰 O가 우리를 도울 수 있습니까?

예, 더 빠른 방법이 있습니다! 배우는 데 시간이 걸리지만 효과가 있고... 꽤 빠르게 작동합니다. 당신도 그것을 시도 할 수 있지만 각 단계에서 시간을 들여 제자리를 잃지 마십시오.

덱을 정렬하는 이 새로운 방법에서 우리는 얼마 전에 했던 방식으로 카드 쌍을 확인하지 않습니다. 이 덱을 정렬하는 새로운 규칙은 다음과 같습니다.

하나: 우리가 지금 작업하고 있는 덱에서 한 장의 카드를 선택합니다. 당신이 원한다면 나를 위해 하나를 선택할 수 있습니다. (처음 이 작업을 수행할 때 "지금 작업 중인 데크의 일부"는 물론 전체 데크입니다.)

Two: 나는 당신이 선택한 그 카드의 덱을 펼칩니다. 이 연기는 무엇입니까? 나는 어떻게 놀까? 글쎄, 나는 시작 카드부터 하나씩 아래로 이동하고 스플레이 카드보다 높은 카드를 찾습니다.

3: 나는 엔드 카드에서 위로 가고, 나는 스플레이 카드보다 더 낮은 카드를 찾습니다.

이 두 장의 카드를 찾으면 교환하고 계속해서 교환할 카드를 더 찾습니다. 즉, 2단계로 돌아가서 선택한 카드를 더 펼칩니다.

어느 시점에서 이 루프(2에서 3으로)가 종료됩니다. 이 탐색의 양쪽 절반이 스플레이 카드에서 만나면 끝납니다. 그런 다음 1단계에서 선택한 카드로 덱을 펼쳤습니다. 이제 시작 지점에 있는 모든 카드는 스플레이 카드보다 낮습니다. 그리고 끝에 있는 카드는 스플레이 카드보다 높습니다. 멋진 트릭!

4개(이것이 재미있는 부분입니다): 이제 두 개의 작은 덱이 있습니다. 하나는 스플레이 카드보다 낮고 하나는 더 높습니다. 이제 각 작은 데크에서 1단계로 이동합니다! 즉, 첫 번째 작은 데크의 1단계부터 시작하여 작업이 완료되면 다음 작은 데크의 1단계부터 시작합니다.

나는 데크를 여러 부분으로 나누고 각 부분을 더 작은 것, 더 작은 것, 그리고 더 이상 할 일이 없을 때 정렬합니다. 이제 이것은 모든 규칙에 따라 느려 보일 수 있습니다. 그러나 저를 믿으십시오. 전혀 느리지 않습니다. 물건을 분류하는 첫 번째 방법보다 훨씬 적은 작업입니다!

이런 종류를 무엇이라고 합니까? 퀵 정렬이라고 합니다! 그 종류는 CAR Hoare 라는 사람이 만들었고 그는 그것을 Quick Sort라고 불렀습니다. 이제 Quick Sort가 항상 사용됩니다!

빠른 정렬은 큰 덱을 작은 덱으로 나눕니다. 즉, 큰 작업을 작은 작업으로 나눕니다.

흠. 거기에 규칙이 있을 수 있다고 생각합니다. 큰 일을 작게 만들려면 쪼개라.

이 종류는 상당히 빠릅니다. 얼마나 빨리? Big O는 다음과 같이 알려줍니다. 이 정렬은 평균의 경우 O(n log n) 작업을 수행해야 합니다.

첫 번째 종류보다 더 빠르거나 덜 빠릅니까? 빅오, 도와주세요!

첫 번째 정렬은 O(n 제곱)입니다. 그러나 빠른 정렬은 O(n log n)입니다. 큰 n에 대해 n log n이 n 제곱보다 작다는 것을 알고 있습니까? 글쎄, 그것이 우리가 빠른 정렬이 빠르다는 것을 아는 방법입니다!

데크를 정렬해야 한다면 어떤 방법이 가장 좋을까요? 글쎄, 당신은 당신이 원하는 것을 할 수 있지만 나는 빠른 정렬을 선택합니다.

빠른 정렬을 선택하는 이유는 무엇입니까? 물론 일하기 싫다! 가능한 빨리 일을 끝내고 싶습니다.

빠른 정렬이 덜 작동하는지 어떻게 알 수 있습니까? O(n log n)이 O(n 제곱)보다 작다는 것을 알고 있습니다. O가 더 작기 때문에 빠른 정렬이 덜 수월합니다!

이제 당신은 내 친구 Big O를 알고 있습니다. 그는 우리가 덜 일하도록 도와줍니다. 그리고 큰 O를 안다면 당신도 일을 덜 할 수 있습니다!

당신은 저와 함께 모든 것을 배웠습니다! 당신은 정말 똑똑합니다! 정말 고맙습니다!

이제 일은 끝났으니 놀러 가자!

---

[1]: 한 번에 1부터 n까지 모든 것을 속임수에 추가하는 방법이 있습니다. Gauss라는 이름의 어떤 아이는 그가 8살 때 이것을 발견했습니다. 나는 그렇게 똑똑 하지 않습니다. 그러니 그가 어떻게 했는지 묻지 마십시오 .

답변자 : nitin kumar

나는 시간 복잡도를 계산하기 위한 가장 일반적인 메트릭이 Big O 표기법인 시간 복잡도를 이해하는 더 간단한 방법을 가지고 있습니다. 이것은 N이 무한대에 접근할 때 N과 관련하여 실행 시간을 추정할 수 있도록 모든 상수 요소를 제거합니다. 일반적으로 다음과 같이 생각할 수 있습니다.

 statement;

일정합니다. 명령문의 실행 시간은 N과 관련하여 변경되지 않습니다.

 for ( i = 0; i < N; i++ ) statement;

선형입니다. 루프의 실행 시간은 N에 정비례합니다. N이 두 배가 되면 실행 시간도 비례합니다.

 for ( i = 0; i < N; i++ ) { for ( j = 0; j < N; j++ ) statement; }

2차입니다. 두 루프의 실행 시간은 N의 제곱에 비례합니다. N이 두 배가 되면 실행 시간이 N * N만큼 증가합니다.

 while ( low <= high ) { mid = ( low + high ) / 2; if ( target < list[mid] ) high = mid - 1; else if ( target > list[mid] ) low = mid + 1; else break; }

로그입니다. 알고리즘의 실행 시간은 N을 2로 나눌 수 있는 횟수에 비례합니다. 이는 알고리즘이 반복할 때마다 작업 영역을 절반으로 나누기 때문입니다.

 void quicksort ( int list[], int left, int right ) { int pivot = partition ( list, left, right ); quicksort ( list, left, pivot - 1 ); quicksort ( list, pivot + 1, right ); }

N * 로그( N )입니다. 실행 시간은 로그인 N 루프(반복 또는 재귀)로 구성되므로 알고리즘은 선형과 로그의 조합입니다.

일반적으로 1차원의 모든 항목으로 작업을 수행하는 것은 선형이고 2차원의 모든 항목으로 작업을 수행하는 것은 2차이며 작업 영역을 반으로 나누는 것은 로그입니다. 3차, 지수 및 제곱근과 같은 다른 Big O 측정값이 있지만 거의 일반적이지 않습니다. Big O 표기법은 측정값인 O( )로 설명됩니다. 퀵소트 알고리즘은 O ( N * log ( N ) )로 설명됩니다.

참고: 이 중 어느 것도 최고, 평균 및 최악의 측정을 고려하지 않았습니다. 각각 고유한 Big O 표기법이 있습니다. 또한 이것은 매우 간단한 설명입니다. Big O는 가장 일반적이지만 내가 보여준 것보다 더 복잡합니다. 큰 오메가, 작은 오, 큰 세타와 같은 다른 표기법도 있습니다. 알고리즘 분석 과정 외에는 만나지 못할 것입니다.

• 더 보기: 여기

답변자 : raaz

Amazon에서 Harry Potter: Complete 8-Film Collection [Blu-ray]를 주문하고 동시에 동일한 영화 컬렉션을 온라인으로 다운로드한다고 가정해 보겠습니다. 어떤 방법이 더 빠른지 테스트하고 싶습니다. 배송이 도착하는 데 거의 하루가 걸리고 다운로드는 약 30분 일찍 완료됩니다. 엄청난! 그래서 치열한 경쟁이다.

반지의 제왕, 황혼, 다크 나이트 3부작 등과 같은 여러 Blu-ray 영화를 주문하고 동시에 모든 영화를 온라인으로 다운로드하면 어떻게 됩니까? 이번에도 배송이 완료되는 데 하루가 걸리지만 온라인 다운로드는 완료하는 데 3일이 걸립니다. 온라인 쇼핑의 경우 구매 수량(입력)은 배송 시간에 영향을 미치지 않습니다. 출력은 일정합니다. 이것을 O(1) 이라고 합니다.

온라인 다운로드의 경우 다운로드 시간은 동영상 파일 크기(입력)에 정비례합니다. 이것을 O(n) 이라고 합니다.

실험을 통해 우리는 온라인 쇼핑이 온라인 다운로드보다 확장된다는 것을 알고 있습니다. 빅오 표기법을 이해하는 것은 알고리즘의 확장 성과 효율성 을 분석하는 데 도움이 되기 때문에 매우 중요합니다.

참고: Big O 표기법은 알고리즘 의 최악의 시나리오를 나타냅니다. O(1) 과 O(n) 이 위의 예에서 최악의 시나리오라고 가정해 봅시다.

참조 : http://carlcheo.com/compsci

답변자 : Kjartan

크기가 n 인 데이터 세트로 작업을 수행해야 하는 알고리즘 A 에 대해 이야기하고 있다고 가정합니다.

그런 다음 O( <some expression X involving n> ) 는 간단한 영어로 다음을 의미합니다.

A를 실행할 때 운이 없다면 완료하는 데 X(n) 작업만큼 걸릴 수 있습니다.

실제로 자주 발생하는 경향이 있는 특정 기능( X(n)의 구현 으로 생각하십시오)이 있습니다. 이것들은 잘 알려져 있고 쉽게 비교할 수 있습니다(예: 1 , Log N , N , N^2 , N! 등).

A와 다른 알고리즘에 대해 이야기 할 때 다음을 비교하여, 그들이 (최악의 경우)을 완료해야하는 작업의 수에 따라 알고리즘을 평가하기 쉽습니다.

일반적으로 우리의 목표는 가능한 한 낮은 숫자를 반환하는 함수 X(n) 을 갖도록 알고리즘 A를 찾거나 구조화하는 것입니다.

답변자 : user1084944

머리에 무한대에 대한 적절한 개념이 있다면 매우 간단한 설명이 있습니다.

Big O 표기법은 무한히 큰 문제를 푸는 데 드는 비용을 알려줍니다.

그리고 더 나아가

상수 요인은 무시할 수 있습니다.

알고리즘을 두 배 빠르게 실행할 수 있는 컴퓨터로 업그레이드하면 큰 O 표기법에서는 이를 알아차리지 못합니다. 상수 요인 개선은 큰 O 표기법이 작동하는 규모에서조차 알아차리기에는 너무 작습니다. 이것은 큰 O 표기법 설계의 의도적인 부분입니다.

그러나 상수 요소보다 "더 큰" 것은 감지할 수 있습니다.

크기가 거의 무한대로 간주될 만큼 "큰" 계산을 수행하는 데 관심이 있는 경우 큰 O 표기법은 대략 문제 해결 비용입니다.

---

위의 내용이 이해가 되지 않는다면 머리 속에 호환 가능한 직관적인 무한대 개념이 없는 것이므로 위의 모든 사항을 무시해야 합니다. 이러한 아이디어를 엄격하게 만들거나 이미 직관적으로 유용하지 않은 경우 설명하는 유일한 방법은 먼저 큰 O 표기법이나 이와 유사한 것을 가르치는 것입니다. (하지만 나중에 큰 O 표기법을 잘 이해하게 되면 이러한 아이디어를 다시 검토해 볼 가치가 있을 것입니다.)

답변자 : AbstProcDo

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

매우 빠른 참고:

"Big O"의 O는 "Order"(또는 정확히 "order of")를 나타냅니다.
그래서 당신은 문자 그대로 그것들을 비교할 무언가를 주문하는 데 사용된다는 아이디어를 얻을 수 있습니다.

• "Big O"는 두 가지 작업을 수행합니다.

  1. 컴퓨터가 작업을 수행하기 위해 적용하는 방법의 단계 수를 추정합니다.
  2. 그것이 좋은지 아닌지를 결정하기 위해 다른 사람들과 비교하는 과정을 촉진합니까?
  3. "Big O'는 표준화된 Notations 위의 두 가지를 달성합니다.

• 가장 많이 사용되는 7가지 표기법이 있습니다.

  1. 1 단계로 작업을 완료한다는 것을 의미합니다. 훌륭합니다. Ordered No.1
  2. logN 단계로 작업을 완료함을 의미합니다. 양호, 주문 번호 2
  3. O(N), N 단계로 작업 완료, 공정한 주문 번호 3
  4. O(NlogN), O(NlogN) 단계로 작업 종료, 좋지 않음, 주문 번호 4
  5. O(N^2), N^2 단계로 작업 완료, 불량입니다 주문 번호 5
  6. O(2^N), 2^N 단계로 작업을 완료하십시오. 끔찍합니다. 주문 번호 6
  7. O(N!), N으로 작업을 완료하십시오 N! 단계, 그것은 끔찍, 주문 번호 7

O(N^2) 표기법을 얻는다고 가정해 봅시다. 메소드가 작업을 수행하기 위해 N*N 단계를 거쳐야 한다는 것이 분명할 뿐만 아니라 순위에서 O(NlogN)

더 나은 이해를 위해 줄 끝의 순서에 유의하십시오. 모든 가능성을 고려하면 7개 이상의 표기법이 있습니다.

CS에서 작업을 수행하기 위한 일련의 단계를 알고리즘이라고 합니다.
용어에서 Big O 표기법은 알고리즘의 성능이나 복잡성을 설명하는 데 사용됩니다.

또한 Big O는 최악의 경우를 설정하거나 상한 단계를 측정합니다.
최상의 경우 Big-Ω(Big-Omega)를 참조할 수 있습니다.

Big-Ω(Big-Omega) 표기(품) | 칸아카데미

• 요약
  "Big O"는 알고리즘의 성능을 설명하고 평가합니다.

  또는 이를 공식적으로 처리하는 경우 "Big O"는 알고리즘을 분류하고 비교 프로세스를 표준화합니다.

답변자 : Shivprasad Koirala

정의 : - Big O 표기법은 데이터 입력이 증가할 경우 알고리즘 성능이 어떻게 수행되는지를 나타내는 표기법입니다.

알고리즘에 대해 이야기할 때 알고리즘의 입력, 출력 및 처리의 3가지 중요한 기둥이 있습니다. Big O는 데이터 입력이 증가하면 알고리즘 처리의 성능이 얼마나 변하는지를 나타내는 기호 표기법입니다.

Big O Notation 을 코드 예제와 함께 자세히 설명하는 이 youtube 비디오를 보는 것이 좋습니다.

예를 들어 알고리즘에 5개의 레코드가 필요하고 이를 처리하는 데 필요한 시간이 27초라고 가정합니다. 이제 레코드를 10으로 늘리면 알고리즘은 105초가 걸립니다.

간단히 말해서 소요 시간은 레코드 수의 제곱입니다. 이것을 O(n ^ 2) 로 나타낼 수 있습니다. 이 상징적 표현을 Big O 표기법이라고 합니다.

이제 단위는 입력의 모든 것이 될 수 있으며 바이트, 레코드의 비트 수, 성능은 초, 분, 일 등과 같은 모든 단위로 측정할 수 있습니다. 따라서 정확한 단위가 아니라 관계입니다.

예를 들어 컬렉션을 가져와 첫 번째 레코드에서 처리하는 아래 함수 "Function1"을 보십시오. 이제 이 기능의 경우 1000, 10000 또는 100000개의 레코드를 입력해도 성능이 동일합니다. 따라서 O(1) 로 나타낼 수 있습니다.

 void Function1(List<string> data) { string str = data[0]; }

이제 아래 함수 "Function2()"를 참조하십시오. 이 경우 레코드 수에 따라 처리 시간이 늘어납니다. O(n) 을 사용하여 이 알고리즘 성능을 나타낼 수 있습니다.

 void Function2(List<string> data) { foreach(string str in data) { if (str == "shiv") { return; } } }

알고리즘에 대한 Big O 표기법을 볼 때 성능의 세 가지 범주로 분류할 수 있습니다.

1. 로그 및 상수 범주: 모든 개발자는 이 범주에서 알고리즘 성능을 보고 싶어합니다.
2. 선형: 개발자는 마지막 옵션이나 유일한 옵션이 남을 때까지 이 범주의 알고리즘을 보고 싶지 않습니다.
3. 기하급수적 :- 이것은 우리가 알고리즘을 보고 싶지 않고 재작업이 필요한 곳입니다.

따라서 Big O 표기법을 보고 알고리즘의 좋은 영역과 나쁜 영역을 분류합니다.

샘플 코드와 함께 Big O에 대해 설명하는 이 10분 분량의 비디오를 시청하는 것이 좋습니다.

https://www.youtube.com/watch?v=k6kxtzICG_g

답변자 : developer747

그것을 보는 가장 간단한 방법 (일반 영어)

우리는 입력 매개변수의 수가 알고리즘의 실행 시간에 어떤 영향을 미치는지 알아보려고 합니다. 애플리케이션의 실행 시간이 입력 매개변수의 수에 비례하면 n의 Big O에 있다고 합니다.

위의 진술은 좋은 시작이지만 완전히 사실이 아닙니다.

보다 정확한 설명(수학적)

가정하다

n=입력 매개변수의 수

T(n)= 알고리즘의 실행 시간을 n의 함수로 표현하는 실제 함수

c= 상수

f(n)= 알고리즘의 실행 시간을 n의 함수로 표현하는 근사 함수

그런 다음 Big O에 관한 한 근사 f(n)은 아래 조건이 참인 한 충분히 좋은 것으로 간주됩니다.

 lim T(n) ≤ c×f(n) n→∞

방정식은 n이 무한대에 가까워짐에 따라 n의 T가 n의 c 곱하기 f보다 작거나 같습니다.

큰 O 표기법에서 이것은 다음과 같이 쓰여집니다.

 T(n)∈O(n)

이것은 n의 T가 n의 큰 O에 있기 때문에 읽습니다.

영어로 돌아가기

위의 수학적 정의에 따라 알고리즘이 n의 Big O라고 말하면 n(입력 매개변수의 수) 이상의 함수임을 의미합니다. 알고리즘이 n의 Big O인 경우 자동으로 n제곱의 Big O이기도 합니다.

Big O of n은 내 알고리즘이 최소한 이것만큼 빠르게 실행됨을 의미합니다. 알고리즘의 Big O 표기법을 보고 느리다고 말할 수 없습니다. 빠르다고만 말할 수 있습니다.

확인 이 UC 버클리에서 큰 O에 대한 비디오 자습서를 위해 밖으로. 사실 단순한 개념입니다. Shewchuck 교수(일명 신급 교사)가 설명하는 것을 들으면 "아, 그게 다야!"라고 말할 것입니다.

답변자 : shanwije

나는 특히 수학에 별로 관심이 없는 사람을 위해 큰 O 표기법에 대한 정말 훌륭한 설명을 찾았습니다.

https://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/

Big O 표기법은 컴퓨터 과학에서 알고리즘의 성능이나 복잡성을 설명하는 데 사용됩니다. Big O는 특히 최악의 시나리오를 설명하며 알고리즘에 필요한 실행 시간 또는 사용된 공간(예: 메모리 또는 디스크)을 설명하는 데 사용할 수 있습니다.

Programming Pearls 또는 기타 컴퓨터 과학 책을 읽고 수학에 대한 기초가 없는 사람은 O(N log N) 또는 기타 겉보기에 미친 구문을 언급하는 장에 도달했을 때 벽에 부딪혔을 것입니다. 이 기사가 Big O 및 Logarithms의 기본 사항을 이해하는 데 도움이 되기를 바랍니다.

첫 번째는 프로그래머이고 두 번째는 수학자(또는 세 번째나 네 번째)로서 Big O를 완전히 이해하는 가장 좋은 방법은 코드로 몇 가지 예제를 생성하는 것입니다. 따라서 다음은 가능한 경우 설명 및 예와 함께 몇 가지 일반적인 성장 순서입니다.

오(1)

O(1)은 입력 데이터 세트의 크기에 관계없이 항상 같은 시간(또는 공간)에서 실행되는 알고리즘을 설명합니다.

 bool IsFirstElementNull(IList<string> elements) { return elements[0] == null; }

에)

O(N)은 성능이 선형으로 그리고 입력 데이터 세트의 크기에 정비례하여 증가하는 알고리즘을 설명합니다. 아래의 예는 또한 Big O가 최악의 성능 시나리오를 선호하는 방법을 보여줍니다. for 루프를 반복하는 동안 일치하는 문자열을 찾을 수 있으며 함수는 일찍 반환되지만 Big O 표기법은 항상 알고리즘이 최대 반복 횟수를 수행하는 상한선을 가정합니다.

 bool ContainsValue(IList<string> elements, string value) { foreach (var element in elements) { if (element == value) return true; } return false; }

오(N ² )

O(N ² )는 성능이 입력 데이터 세트 크기의 제곱에 정비례하는 알고리즘을 나타냅니다. 이는 데이터 세트에 대한 중첩 반복을 포함하는 알고리즘에서 일반적입니다. 더 깊은 중첩 반복은 O(N ³ ), O(N ⁴ ) 등이 됩니다.

 bool ContainsDuplicates(IList<string> elements) { for (var outer = 0; outer < elements.Count; outer++) { for (var inner = 0; inner < elements.Count; inner++) { // Don't compare with self if (outer == inner) continue; if (elements[outer] == elements[inner]) return true; } } return false; }

오( ^2N )

O(2 ^N )은 입력 데이터 세트에 추가할 때마다 2배씩 증가하는 알고리즘을 나타냅니다. O(2 ^N ) 함수의 성장 곡선은 기하급수적입니다. 매우 얕게 시작하여 급격히 상승합니다. O(2 ^N ) 함수의 예는 피보나치 수의 재귀 계산입니다.

 int Fibonacci(int number) { if (number <= 1) return number; return Fibonacci(number - 2) + Fibonacci(number - 1); }

로그

로그는 설명하기가 약간 까다롭기 때문에 일반적인 예를 사용하겠습니다.

이진 검색은 정렬된 데이터 세트를 검색하는 데 사용되는 기술입니다. 기본적으로 중앙값인 데이터 세트의 중간 요소를 선택하여 작동하고 이를 목표 값과 비교합니다. 값이 일치하면 성공을 반환합니다. 목표 값이 프로브 요소의 값보다 높으면 데이터 세트의 상위 절반을 가져와 동일한 작업을 수행합니다. 마찬가지로 목표 값이 프로브 요소의 값보다 낮으면 하위 절반에 대해 작업을 수행합니다. 값을 찾거나 더 이상 데이터 세트를 분할할 수 없을 때까지 반복할 때마다 데이터 세트를 계속 절반으로 줄입니다.

이러한 유형의 알고리즘은 O(log N)으로 설명됩니다. 이진 검색 예제에 설명된 데이터 세트의 반복적인 반감기는 데이터 세트의 크기가 증가함에 따라 처음에 정점에 도달하고 천천히 평평해지는 성장 곡선을 생성합니다. 예를 들어 10개 항목을 포함하는 입력 데이터 세트를 완료하는 데 1초가 걸립니다 100개 항목을 포함하는 데이터 세트는 2초가 걸리고 1000개 항목을 포함하는 데이터 세트는 3초가 걸립니다. 입력 데이터 세트의 크기를 두 배로 늘리는 것은 알고리즘의 단일 반복 후에 데이터 세트가 절반으로 줄어들고 따라서 입력 데이터 세트의 절반 크기와 동등하므로 성장에 거의 영향을 미치지 않습니다. 이것은 대용량 데이터 세트를 다룰 때 바이너리 검색과 같은 알고리즘을 매우 효율적으로 만듭니다.

답변자 : nkt

이것은 매우 간단한 설명이지만 가장 중요한 세부 사항을 다루기를 바랍니다.

문제를 처리하는 알고리즘이 몇 가지 '요인'에 의존한다고 가정해 봅시다. 예를 들어 N과 X로 합시다.

N 및 X에 따라 알고리즘에는 몇 가지 작업이 필요합니다. 예를 들어 WORST의 경우 3(N^2) + log(X) 작업입니다.

Big-O는 상수 인자(일명 3)에 대해 그다지 신경 쓰지 않기 때문에 알고리즘의 Big-O는 O(N^2 + log(X)) 입니다. 기본적으로 '최악의 경우에 알고리즘이 필요한 작업의 양'으로 변환됩니다.

출처 : Here

출처 : http:www.stackoverflow.com/questions/487258/what-is-a-plain-english-explanation-of-big-o-notation">