Big O에서 O는 무엇입니까?

음, 내 추측으로는 wikipedia와 일치 하는 순서 일 것입니다.

편집 : (내 자신의 (개선 사항 감사)) 독일어 위키 백과 문서

순서 (독일어 : “Ordnung von”)의 상징으로 사용 된 대문자 O (당시에는 대문자 오크 론)는 독일의 숫자 이론가 인 Paul Bachman은 분석적인 숫자 이론에 관한 그의 저서 2 호에서 1894 년에 나왔습니다. 독일어 용어.

댓글

• 많은 수학자들이 언급 한 경우 일 수 있습니다. 따라서 원래는 그렇지 않았습니다. 20 세기 초 숫자 이론 책을 읽으면 그러한 설명을 찾을 수 없습니다. 그것이 바로 그게 사실이고 나는 그의 생각이 표기법에 어떤 것인지 알아 내기 위해 독일어를 읽을 수는 없습니다. ‘.
• @Jonathan : 게시물이 업데이트되었습니다.
• 아주 좋습니다! 수 이론 책을 모두 살펴 봤는데 ‘ 어디서도 O에 대한 설명을 찾을 수 없었습니다. +1
• ‘ O는 그다지 의미가 없다고 말하면서 항상 순서 로 발음했습니다.
• 매우 유익합니다! 그래도-프로그래머가 O를 ‘ 오 ‘로 발음하는 이유는 무엇입니까?

“큰”은 “자본”을 의미하고 “O”는 “복잡성의 순서”와 같이 순서를 의미합니다. 예를 들어 대문자 “O”또는 “Big O”와 같이 “복잡도 순서”를 O (f (x))로 작성하는 관례 때문에 이름이 지정되었습니다. “모두”가 의미하는 바를 이해하고 이해하는 것은 복잡도 분석을 이해하는 데 실제로 도움이되지 않기 때문에 아무도 그것에 대해 많이 이야기하지 않습니다.

복잡성 분석에 대한 이해를 위해 topgun_ivard가 게시 한 링크는 시작하기 좋은 곳입니다. 데이터 구조 또는 알고리즘을 다루는 좋은 입문 교과서도 도움이 될 수 있습니다.

댓글

• I ‘ 죄송합니다.하지만 Bachmann-Landau 표기법은 독일 수학자에 의해 발명 되었기 때문에 그가 영어 단어의 이름을 따서 명명했을 것 같지 않습니다. 사실, 그것이 에 의해 발명 되었더라도 미국의 수학자라면 독일어 단어의 이름을 따서 명명되었을 것입니다. 왜냐하면 그것이 발명되었을 때 (제 생각에는 1920 년경) 수학의 국제 언어가 독일어 였기 때문입니다. 또한 독일어가 아니 었습니다. ‘ 원격으로 복잡성과 관련이 없습니다.
• @J ö rg : 예,하지만 ‘ 그것은 단지 Ordnung 일 뿐이며, 독일 위키 기사가 출처라고 주장하는 : de.wikipedia.org/wiki/Landau-Symbole#Geschichte
• @Ethel 내가 투표 할 수 있도록 기사를 약간 변경해 주시겠습니까? 당신은 정말 맞습니다. 투표하기 전에 수정해야합니다.
• @Jonathan, 저는 ‘ 원하는 사소한 변경이 정확히 무엇인지 잘 모르겠습니다. 계속해서 원하는대로 편집 할 수 있습니까? 또는 back2dos ‘ 답변을 그대로 둘 수 있습니다. 훌륭한 연구 결과로 인해 어쨌든 최고의 답변을 얻은 것 같습니다. 🙂
• 흠 , 흥미 롭습니다. 스웨덴에서 Big Oh는 일반적으로 iv id = “ddaf911adb”가 아니라 ” ordo ” (라틴어 for, well, order)라고합니다. >

O 는 주문을 나타냅니다.

독일의 수학자 Paul Bachmann이 수 이론에 관한 그의 책 Die Analytische Zahlentheorie 의 두 번째 책에서 처음 소개했습니다. 1894 년 출판 (p. 401) . 그는 처음으로 표기법을 사용한 공식 뒤에 다음과 같이 기록합니다.

(…) wenn wir durch das Zeichen O (n) einde Grösse ausdrücken, deren Ordnung in Bezug auf n die Ordnung von n nicht überschreitet (…)

내 번역 :

(…) 여기서 O (n) 표기법으로 n 을 참조하는 순서가 n 순서를 초과하지 않는 크기를 나타냅니다 (…)

다른 사람들이 말한 것과 달리 그의 텍스트에는 이것이 실제로 그리스 수도 오 미크론이라는 것을 나타내는 것은 없습니다. 그는 그리스어와 라틴어 문자를 많이 사용하기 때문에 “말할 방법이 전혀 없습니다.”텍스트에서 “Ordnung n log n “등을 계속 사용했음을 감안할 때 어쨌든 “Ordnung”(의심이 있다면 “주문”을 의미하는 독일어)을 의미하지만 그래도 멋진 그리스어 O를 사용할 수 있습니다.

그러나 omikron의 기원은 다음과 같습니다. 그의 논문 Big Omicron 및 Big Omega 및 Big Theta에서 관련 개념에 대해 기호 오메가 (Ω) 및 세타 (Θ)를 도입 한 Donald Knuth 덕분에 역풍 일 가능성이 높습니다. 또는 이전에 오메가 기호를 도입 한 Hardy and Littlewood

댓글

• 흥미 롭습니다. 나는 당신이 옳다고 생각합니다. 방금 Landau ‘와 Bachmann ‘의 책에서 정의를 찾아 봤는데 실제로 a) 라틴어를 사용합니다. a 그리스어 Omikron, b) 둘 다 ” Ordnung “라는 단어를 사용하고 c) Landau는 명시 적으로 ” Ordnung “를 의미합니다. 나는 바로 잡았다.
• 어떤 더 나은 단어를 찾을 수 있을까? 내 말은, 독일 사람? Ordnung ist das halbe Leben!
• 정답, 찬성, 멋진 답변의 첫 문장은 다음과 같아야합니다. ‘ O는 ” Ordnung ” (독일어는 ” 주문 ” 의미) . ‘이 답변은 다른 독자의 관심을 끄는 데 도움이됩니다.

이 기사 가 마음에 듭니다.이 기사도 유용하길 바랍니다.

기사에서 한 섹션 인용 :
Big Greek Letters

Big O는 종종 오용됩니다. Big O 또는 Big Oh는 실제로 Big Omicron의 약자입니다. 점근 적 복잡성의 상한을 나타냅니다. 따라서 알고리즘이 O (n log n)이면 상한이 cn log n이되는 상수 c가 존재합니다.

Θ (n log n) (Big Theta)는 그보다 더 밀접하게 바인딩됩니다. 이러한 알고리즘은 c1n log n < f (n) < c2n log n과 같은 두 개의 상수 c1 및 c2가 있음을 의미합니다.

편집 : 내가 틀렸다는 것이 밝혀졌습니다. 그럼에도 불구하고 이것은 누군가가 기호를 똑바로 유지하는 데 도움이 될 수 있으므로 삭제하지 않겠습니다.

사실 라틴 문자는 아닙니다 . 아 , 그리스 문자 Omicron 입니다. 안타깝게도이 두 글자는 똑같은 글리프를 가지고 있으므로 시간이 지남에 따라 원래 버전이 손상되어 이제는 아 .

기호의 선택은 실제로 특별한 의미가 없으며 니모닉 장치로 선택되었습니다.

• Omicron 에는 MICRO라는 문자가 포함되어 있으며 Omicron 기호의 의미는 대략 “보다 작음”을 의미합니다.
• Omega 에는 MEGA라는 문자가 있습니다. , 오메가 기호의 의미는 대략 “보다 큼”을 의미합니다.
• Theta (Θ)는 등호처럼 보입니다. , 그리고 Theta 기호의 의미는 대략 “같음”을 의미합니다.

그게 다입니다. 진짜 의미는 없습니다. 의미를 기억하는 데 도움이 될 것입니다. 당연히.

댓글

• 당신의 니모닉 제안을 믿고 싶지만 (정말 멋진 아이디어입니다) 이것이 Bachmann의 실제 원래 의도라는 증거입니다. 제공하면 ‘ 당신을 +1 할 것입니다.
• @Jonathan Henson : 분명히 Knuth 교수에게 오해를당했습니다. 🙂

“f (x)는 g (x)의 큰 오입니다.”

함수의 성장을 예측하는 수학적 방법입니다.

f와 g를 정수 세트 또는 세트 또는 실수에서 실수 세트까지의 함수라고합시다. | f (x) |와 같은 상수 C와 k가 있으면 f (x)는 O (g (x))라고 말합니다. < = C | g (x) | x> k.

당신은 이것을 “f (x) is big-oh of g (x)”라고 읽을 것입니다.

big-O는 때때로 Landau 기호라고 불립니다. 독일의 수학자 에드먼드 란다 우. 나는 그것이 그 이상의 어떤 것을 의미한다고 생각하지 않습니다. 당신은 또한 유사한 big-Omega 및 big-Theta 표기법을 가지고 있습니다. 기호는 삼각형의 각도를 나타 내기 위해 항상 세타를 사용하여 고등학교 평면 기하학에있었습니다. 클래스.

수정 @ back2dos는 주문을 참조하는 O에 대한 만족스러운 설명을 제공했습니다. Job. 그의 대답을보십시오.

Donald Knuth는 그것을 컴퓨터 프로그램의 복잡성을 연구하는 데 적용했습니다.

표기법이 사용 된 이유를 찾으려면 읽어야합니다

“Analytische Zahlentheorie”(1892 년 Paul Bachmann 저)

업데이트 : 내 대답을 정리하고 더 정확 해 지려고 시도하는 것은

Big O 표기법은 성장률에 따라 함수를 특성화하는 방법입니다. 순서를 의미합니다 (첫 번째 순서는 n 제곱이되는 n 두 번째 순서 등). 이것은 N 개의 요소가 주어진 메소드 런타임 (또는 스토리지)에 대한 최악의 시나리오입니다. 메서드가 수행하는 가장 나쁜 순서가 클수록.
예를 들어 배열에서 레코드를 찾는 것은 O (1)입니다 (해시 테이블의 일부 구현도 마찬가지라고 생각합니다). 링크 목록의 끝에 값을 추가하면 O (N)이됩니다. 요소 등을 추가하기 전에 목록의 끝에 도달해야하기 때문입니다.

이 답변은 다음보다 약간 더 정확해야합니다. 나의 첫 번째 시도 🙂

댓글

• -1 이것은 단지 평범한 틀린 잘못된 것이고 요청 된 것과는 별도의 질문에 답했기 때문입니다. 문제는 ” O ” 문자가 사용되는 이유가 아니라 ” Big O 표기법이 작동합니까? “. Big-oh의 작동 방식에 대해 ‘ 정확하지 않지만 배열을 반복하는 것은 O (n)이고 여기서 n은 O (1)이 아니라 배열의 크기입니다. . 표기법은 알고리즘의 “주기 “와는 아무 관련이 없습니다 … it ‘ 알고리즘 실행 시간의 상한을 측정 한 것입니다.
• 여기서 여러분과 논쟁하는 것은 아니지만 ‘이 의미하는 바입니다. 런타임은 무엇을 의미합니까?음, 실행 시간은 컴퓨터에서 처리해야하는 항목에 따라 결정됩니다. 나는 여기에서 자유롭게 순환을 사용한다고 생각합니다. 주기적으로 나는 iterate-through 또는 이와 비슷한 것을 말 했어야한다고 생각합니다. 당신은 상한에 대해 맞지만 평균을 결정하지 않습니다. 따라서 다운 그레이드를 수락합니다.