"Big O" 표기법의 평문 영어 설명은 무엇인가요?

가능한 한 형식적인 정의는 최소화하고 간단한 수학을 선호합니다.

답변 1

빠른 참고로, 제 답변은 거의 확실히 상한선을 나타내는 Big Oh notation과 양면 경계를 나타내는 빅세타 표기법인 Θ을 혼동하고 있을 가능성이 매우 높습니다. 그러나 제 경험상 비학술적인 상황에서의 토의에서는 이러한 혼동이 일반적이기 때문에 혼동을 불러일으킨 점에 대해 사과합니다.

이 그래프를 통해 BigOh 복잡성을 시각적으로 표현할 수 있습니다.

빅오 표기법에 대해 내가 제공할 수 있는 가장 간단한 정의는 다음과 같다:

빅 오 표기법은 알고리즘의 복잡도를 상대적으로 나타내는 표기법입니다.

그 문장에 중요하게 선택된 단어들이 있습니다.

친척: 당신은 사과와 사과를 비교할 수밖에 없습니다. 산술 곱셈을 수행하는 알고리즘과 정수 목록을 정렬하는 알고리즘을 비교할 수는 없습니다. 그러나 산술 연산 (하나는 곱셈, 다른 하나는 덧셈)을 수행하는 두 알고리즘을 비교하면 의미 있는 정보를 얻을 수 있습니다.

표현: 간단한 형태의 BigOh는 알고리즘 사이의 비교를 단일 변수로 줄입니다. 이 변수는 관측 또는 가정에 기반하여 선택됩니다. 예를 들어, 정렬 알고리즘은 일반적으로 비교 작업(상대적인 순서를 결정하기 위해 두 노드를 비교하는 작업)에 따라 비교됩니다. 이는 비교가 비싸다는 가정을 기반으로 합니다. 그러나 비교가 저렴하고 교체가 비싸다면 어떻게 될까요? 비교가 변경됩니다.

복잡도: 만약 1만개의 요소를 정렬하는 데 1초가 걸린다면, 100만개를 정렬하는 데는 얼마나 걸릴까요? 이 경우의 복잡도는 다른 것에 상대적인 상대 측정입니다.

나머지를 읽고 나중에 다시 돌아와서 위의 글을 다시 읽으십시오.

빅오의 가장 좋은 예시는 산술 연산을 하는 것입니다. 두 개의 수 (123456 및 789012)를 취합니다. 우리가 학교에서 배운 기본 산술 연산은 다음과 같습니다:

더하기;

빼기;

곱셈; 그리고

분할.

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

더하기는 가장 간단합니다. 숫자를 (오른쪽으로) 정렬하고, 열에 있는 숫자를 더하여 그 덧셈의 마지막 숫자를 결과에 쓰면 됩니다. 해당 숫자의 '십' 부분은 다음 열로 옮겨집니다.

이 알고리즘에서 가장 비싼 작업이 숫자를 더하는 것이라고 가정해 봅시다. 이 두 숫자를 더하기 위해서는 6자리 숫자(때로는 7번째 자리까지 올림)를 더해야 합니다. 만약 100자리 숫자 두 개를 더한다면 총 100번의 덧셈을 해야 하고, 10,000자리 숫자 두 개를 더한다면 10,000번의 덧셈을 해야 합니다.

패턴을 보세요? 복잡도(연산 횟수)는 큰 숫자의 자릿수 n과 직접 비례합니다. 우리는 이것을 O(n) 또는 선형 복잡도라고 부릅니다.

빼기는 비슷합니다 (하지만 올림 대신 빌려야 할 수 있습니다).

곱셈은 다릅니다. 숫자를 정리하고, 아래 숫자의 첫 자리를 가져와 상위 숫자 각 자리와 차례대로 곱하고 각 자릿수를 통해 진행합니다. 따라서 두 개의 6 자리 숫자를 곱하려면 36 번의 곱셈을 해야합니다. 끝 결과를 얻기 위해 10 또는 11 개의 열을 더해야 할 수도 있습니다.

만약 100자리 숫자 두 개가 있다면, 10,000번의 곱셈과 200번의 덧셈이 필요합니다. 100만 자리 숫자 두 개의 경우에는 1조(10^12) 번의 곱셈과 2백만번의 덧셈이 필요합니다.

알고리즘이 n의 제곱으로 확장되는 경우, 이는 O(n 2) 또는 이차 복잡도입니다. 이것은 다른 중요한 개념을 소개하는 좋은 시기입니다.

우리는 복잡성의 가장 중요한 부분만을 생각합니다.

빈틈없는 사람들은 우리가 연산 횟수를 n 2 + 2n으로 표현할 수 있다는 것을 깨달았을 것입니다. 그러나 백만 자리씩 된 두 숫자의 예시에서 보았듯이, 두 번째 항(2n)은 무의미해집니다. (그 단계에서 전체 연산의 0.0002%를 차지합니다.)

여기서 우리는 최악의 경우 시나리오를 가정한 것을 알 수 있습니다. 6 자리 수를 곱할 때 그 중 하나가 4 자리 수이고 다른 하나가 6 자리 수 인 경우, 우리는 여전히 24 개의 곱셈만 있습니다. 그러나 'n'에 대해 최악의 경우 시나리오를 계산합니다. 즉, 두 숫자가 모두 6 자리 숫자 인 경우입니다. 따라서 대문자 Oh 표기법은 알고리즘의 최악의 경우 시나리오에 대한 것입니다.

전화번호부

제가 떠올릴 수 있는 다음으로 좋은 예는 일반적으로 '화이트 페이지' 또는 유사한 이름으로 불리는 전화번호부입니다. 그러나 나는 성과 이름 또는 이니셜로 사람을 나열하고 가능하면 주소와 전화번호를 기재하는 것에 대해 이야기하고 있습니다. 이는 국가에 따라 다를 수 있습니다.

이제 만약 1,000,000개의 이름을 포함하는 전화번호부에서 John Smith의 전화번호를 찾도록 컴퓨터에 명령한다면, 당신은 어떻게 할 것인가요? (S가 어디서 시작하는지 추측할 수 있다는 사실은 무시하겠습니다.)

전형적인 구현 방법은 중간을 열어 500,000 번째를 확인하고 Smith와 비교하는 것입니다. 만약 그것이 Smith, John이면 운좋게 다행입니다. 그러나 더 가능성이 높은 것은 John Smith가 그 이름 앞이나 뒤에 있을 것입니다. 그러면 그게 뒤쪽에 있다면 전화번호부의 뒷 절반을 반으로 나누어 반복합니다. 만약 앞쪽에 있다면 전화번호부의 앞 절반을 반으로 나누어 반복합니다. 그리고 그렇게 계속합니다.

이것은 이진 탐색이라고 하며, 당신이 인지하든 인지하지 않든 매일 프로그래밍에서 사용됩니다.

만약 백만 개의 이름이 있는 전화번호부에서 이름을 찾고 싶다면, 이 과정을 최대 20 번 거침으로써 어떤 이름이든 찾을 수 있습니다. 검색 알고리즘을 비교하면 우리는 이 비교를 'n'으로 결정합니다.

3개의 이름이 있는 전화번호부에는 최대 2개의 비교가 필요합니다.

7에 대해 최대 3까지 걸립니다.

15에 대해서는 4가 소요됩니다.

Sorry, as an AI language model, I need a sentence or context to translate. Please provide the text that needs to be translated.

100 만원에는 20이 걸립니다.

그것은 놀랍도록 좋지 않나요?

빅오 용어로는 O (log n) 또는 로그 형 복잡도입니다. 이 경우의 로그는 ln (기본 e), log 10, log 2 또는 다른 기본 일 수 있습니다. 중요하지 않습니다. 여전히 O (log n)이며 O (2n 2)와 O (100n 2)가 여전히 모두 O (n 2)와 같습니다.

이 시점에서 BigOh는 알고리즘의 세 가지 경우를 결정하는 데 사용될 수 있다는 것을 설명하는 것이 가치가 있다.

최선의 경우: 전화번호부 검색에서 최선의 경우는 한 번의 비교에서 이름을 찾는 것입니다. 이는 O(1) 또는 상수 복잡도입니다.

상황: 위에서 논의한 대로, 이것은 O(log n)입니다.

최악의 경우: 이것도 O(log n)입니다.

보통 우리는 최상의 경우에 대해서는 관심이 없습니다. 우리는 예상되는 최악의 경우와 관심이 있습니다. 때로는 이 중 하나가 더 중요할 수도 있습니다.

전화번호부로 돌아가기.

당신이 전화번호를 가지고 이름을 찾고 싶다면 어떻게 될까요? 경찰은 역방향 전화번호부를 가지고 있지만 이러한 조회는 일반 대중에게는 허용되지 않습니다. 그렇다면 그것들은 있을까요? 기술적으로 보면 일반 전화번호부에서 번호를 역방향으로 조회할 수 있습니다. 어떻게요?

당신은 먼저 이름으로 시작하고 번호를 비교합니다. 일치하면 좋고, 그렇지 않으면 다음으로 이동합니다. 전화번호부는 (어쨌든 번호별로) 정렬되지 않았기 때문에 이렇게해야합니다.

전화번호로 이름 찾기 (역 검색) :

최상의 경우: O(1);

예상되는 경우: O(n) (500,000에 대해)

최악의 경우: O(n) (1,000,000에 대해)

여행하는 영업사원

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

간단해 보이죠? 다시 한번 생각해보세요.

A, B, C 각각의 도시가 서로 연결된 길로 이루어져 있다면, 다음과 같이 이동할 수 있습니다:

A → B → C (A에서 B로, 그리고 B에서 C까지)

A → C → B

B → C → A

B에서 C로 이동하고, 다시 C에서 A로 이동합니다.

B -> A -> C

B에서 A로, 그리고 A에서 C로 이동합니다.

C → A → B

C → A → B로 번역합니다.

C → B → A

C에서 B로 이동하고, 다시 B에서 A로 이동합니다.

실제로는 그 이하입니다. 일부는 동등합니다(예를 들어, A → B → C와 C → B → A는 동등합니다. 동일한 도로를 사용하기 때문입니다. 하지만 방향만 반대입니다).

실제로는, 가능한 경우는 3가지가 있습니다.

이것을 4개의 도시에 가져가면 (iirc) 12가지 가능성이 있습니다.

5면 60입니다.

6가 360이 됩니다.

이것은 팩토리얼이라는 수학적 연산의 기능입니다. 기본적으로:

5! = 5 × 4 × 3 × 2 × 1 = 120이다.

6! = 6 × 5 × 4 × 3 × 2 × 1 = 720

6! = 육곱(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

25! = 25 × 24 × … × 2 × 1 = 15,511,210,043,330,985,984,000,000

I am sorry, as an AI language model, I am unable to determine what text to translate. Please provide me with the text to be translated.

50! = 50 × 49 × ... × 2 × 1 = 3.04140932 × 10 64

여행하는 외판원 문제의 빅오는 O(n!) 이며, 팩토리얼 또는 조합적 복잡성입니다.

200개의 도시에 도달할 때까지 전통적인 컴퓨터로는 문제를 해결하기에는 우주에 남은 시간이 충분하지 않습니다.

생각해 볼 것.

다항 시간

또 하나 언급하고 싶은 점은 복잡도가 O(n a)인 모든 알고리즘은 다항식 복잡도를 가지며 다항식 시간 안에 해결될 수 있다는 것입니다.

O(n), O(n²) 등은 모두 다항식 시간입니다. 일부 문제는 다항식 시간에 해결할 수 없습니다. 이에 따라 세상에는 어떤 것들이 사용됩니다. Public Key Cryptography는 그 대표적인 예입니다. 아주 큰 수의 두 소인수를 찾는 것은 계산적으로 어렵습니다. 그렇지 않았다면, 우리가 사용하는 공개 키 시스템을 사용할 수 없게 됩니다.

어쨌든, 이것이 BigOh에 대한 (희망적으로 평이한 영어로 작성된) 설명입니다 (개정).

답변 2

Big O notation is a way of describing how an algorithm's performance will scale when the size of the inputs grows. It is commonly used in computer science to compare different algorithms and determine which is more efficient.

In simple terms, Big O notation is a mathematical representation of how long it takes an algorithm to solve a problem with a certain number of inputs. The notation is expressed as an equation, where the input size is denoted by n and the time it takes to solve the problem is denoted by O.

For example, an algorithm with a Big O notation of O(n) means that the time it takes to solve the problem will increase proportionally to the size of the input. If the input size is 10, the algorithm will take 10 times longer to solve the problem than if the input size were 1.

On the other hand, an algorithm with a Big O notation of O(n^2) means that the time it takes to solve the problem will increase quadratically with the input size. If the input size is 10, the algorithm will take 100 times longer to solve the problem than if the input size were 1.

In practice, selecting the most efficient algorithm is essential for optimizing program performance. By using Big O notation to compare algorithms and identify the most efficient one, developers can save valuable time and resources.

Translated to Korean:

빅 오 표기법은 입력 크기가 증가할 때 알고리즘 실행 속도의 스케일을 설명하는 방식이다. 이것은 컴퓨터 과학에서 다양한 알고리즘을 비교하고 더 효율적인 것을 파악하는 데 자주 사용된다.

간단하게 말하면, 빅 오 표기법은 알고리즘이 특정한 입력 크기에 대해 문제를 해결하는 데 시간이 얼마나 걸리는지를 나타내는 수학적인 표기법이다. 이 표기법은 입력 크기를 n으로, 문제 해결에 걸리는 시간을 O로 표기된 방정식으로 나타낸다.

예를 들어, 빅 오 표기법이 O(n)인 알고리즘은 입력 크기가 증가할수록 문제 해결에 걸리는 시간도 비례해서 증가한다. 입력 크기가 10이면, 1인 경우보다 10배 더 많은 시간이 걸린다.

반면, 빅 오 표기법이 O(n^2)인 알고리즘은 입력 크기에 대해 시간이 제곱 형태로 증가한다. 입력 크기가 10인 경우, 1인 경우보다 100배 더 많은 시간이 걸린다.

실제로, 프로그램 성능을 최적화하려면 가장 효율적인 알고리즘을 선택하는 것이 중요하다. 빅 오 표기법을 사용하여 알고리즘을 비교하고 가장 효율적인 것을 파악함으로써, 개발자는 소중한 시간과 자원을 절약할 수 있다.