대O, 대오메가와 대오메가 사이에는 어떤 차이가 있습니까?

큰 O 기호보다 더 무서운 컴퓨터 과학 주제가 있습니까?이 이름을 놀라게 하지 마라. 큰 O 기호는 큰 문제가 아니다.이것은 이해하기 쉽다. 너는 수학 천재가 되지 않아도 이해할 수 있다.대O, 대Omega 또는Ω와 대Theta 또는Θ는 알고리즘 계산의 복잡성을 나타내는 기호이다.이 강좌에서 당신은 대O, 대오메가와 대오메가 기호 간의 차이를 배울 것입니다.
만약 당신이 방금 우리에 가입했다면, 당신은 What is Big O Notation?부터 시작하기를 희망할 것입니다.

무엇이 점진적인 계산의 복잡성입니까?

이것은 Wikipedia definition of asymptotic computational complexity:

In computational complexity theory, asymptotic computational complexity is the usage of asymptotic analysis for the estimation of computational complexity of algorithms and computational problems, commonly associated with the usage of the big O notation.

😪
정당하다
어쩐지 이 물건이 배우기 힘들더라니.
우리 이 행어를 분해합시다.

무엇이 점근선입니까?

이것은 또 위키백과입니다. 곡선의 점근선은 다음과 같습니다.

a line such that the distance between the curve and the line approaches zero as one or both of the x or y coordinates tends to infinity.

😕
그래
이러한 정의는 간단한 개념을 더욱 이해하기 어렵게 한다.
우리는 모두 시각 학습자이기 때문에 다음과 같은 등식을 그릴 것이다.

y = 1 / x

x값이 아무리 크든 작든 우리의 곡선은 x나 y축에 영원히 접촉하지 않는다.
이 숫자가 무궁무진해도
🐢🏃‍♀️
특히 이 숫자가 0이라면
왜?
수학적으로 0으로 나눌 수는 없다.
분열은 이 문제를 사고하는 또 다른 방식이다.우리가 0에 도달하기 전에, 우리는 하나를 반으로 나누어 몇 번을 할 수 있습니까?
무한한 의견 차이가 있다!
1의 절반은 ½ 이다.½의 절반은 ¼ 이다.¼의 절반은 ⅛ 이다.⅛의 절반은 1/16 이다.1/16의 절반은... 이게 어떻게 된 일인지 봐.
매번 나눌 때마다 우리의 분모는 2의 멱을 증가시킨다.
우리는 영원히 어떤 것들을 둘로 나눌 수 없다.
케이크가 아니면
🍰
위 그림에서 x축과 y축은 방정식y = 1 / x의 점근선이다.그러나 모든 선은 점근선이 될 수 있다.우리는 수평선과 수직선에 국한되지 않는다.

무엇이 점근 분석입니까?

이해하기 어려운 정의들을 계속 소화합시다.
Wikipedia에 근거하여 점근 분석은 다음과 같다.

a method of describing limiting behavior.

한계는 얼마입니까?
수학에서 극한은 입력의 증가(또는 감소)에 따라 함수에 가까운 값이다.
듣자니 점근선 같다.그러면 우리는 어떻게 점근 분석 함수를 분석합니까?
만약 우리의 함수 f(x)가 x^2 + 2x와 같다면 x의 값이 증가함에 따라 2x에 비해 x^2 중요하지 않게 변할 것이다.
그리고 우리는 간단하게 f(x)가 점점 가까워지는 것이 x^2와 같다고 말한다.

대O, 대오메가와 대오메가 사이에는 어떤 차이가 있습니까?

Introduction to Algorithms에서 Cormen 등은 삽입 정렬을 예로 삼아 대O, 대Omega와 대Theta 간의 차이를 설명한다.우리도 여기서 이렇게 할 거야.다음은 JavaScript에 삽입된 정렬의 구현입니다.

const insertionSort = arr => {
 for (let i = 1; i < arr.length; i++) {
   let index = i;
   while (index > 0 && arr[index - 1] > arr[index]) {
     let temp = arr[index];
     arr[index] = arr[index - 1];
     arr[index - 1] = temp;
     index = index - 1;
   }
 }
 return arr;
}

다음은 삽입 정렬에 대한 빠른 복습(또는 설명)입니다.

우리는 전체 수조를 교체한다.

그룹의 각 요소에 대해 다음을 확인합니다.

인덱스 값이 1보다 크면

색인 이전의 요소가 색인 자체보다 크면

두 조건이 모두 충족되면 교환합니다

무엇이 대O입니까?

대O는 알고리즘의 상계를 나타낸다.
우리의 삽입 정렬 예시를 사용하면 우리 알고리즘의 성장률은 최대 두 번, 또는 O(n^2)이다.
이것이 바로 우리가 개발자와 실천자로서 주로 대O에 관심을 가지는 이유이다.
우리는 알고리즘의 성능이 얼마나 나쁠지 알고 싶다.
정렬을 삽입하는 큰 O가 O(n^2)라고 하는 것은 정렬을 삽입하는 것이 항상 O(n^2)라는 것을 의미하지 않는다.실제 운행 시간은 입력에 따라 달라진다.우리가 말하고자 하는 것은 최악의 경우, 이것은 삽입 정렬 성능의 상한선이다.
이 점을 알고 나면 우리는 자신에게 다음과 같은 질문을 해야 한다.

동의합니까?

우리가 더 잘할 수 있을까?

오메가가 뭐예요?

오메가는 알고리즘의 하한선을 묘사했다.
우리의 삽입 정렬 예시를 사용합니다. 만약 입력이 정렬되었다면, 우리 알고리즘의 성장률은 적어도 선형이거나 Ω(n)입니다.
만약 생활이 항상 우리에게 수조를 정렬해 주었으면 좋겠다.🌼
우리도 이것을 최선의 상황으로 간주할 수 있다.

무엇이 대θ입니까?

대θ는 알고리즘의 경계를 묘사했는데 이것은 위에서 아래로의 극한이다.
삽입 정렬 예시를 사용하면 성장률은 최대 O(n^2), 적어도 Ω(n)라는 것을 알 수 있다.
그러나 대θ는 우리의 입력에 따라 변화한다.우리의 삽입 정렬 예시로 돌아가면 가장 좋은 상황에서 큰 θ는 n이지만 최악의 경우 큰 θ는 n^2이다.삽입 정렬이 Θ(n) 또는Θ(n^2)이라고 말하는 것은 옳지 않습니다. 왜냐하면 이 두 가지는 삽입 정렬이 항상 n이나 n^2에서 실행된다는 것을 의미하기 때문입니다.
그렇게 크면 무슨 소용이 있겠는가?
대테타는 일반적으로 알고리즘의 평균 상황이나 예상 상황을 설명하는 데 쓰인다.이것은 결코 완전히 정확하지는 않지만, 그것은 유용한 속기이다.
삽입 정렬에 대해 대θ의 평균 상황은 n^2이다.

그러면 큰 O, 큰 오메가와 큰 오메가 사이의 차이는 무엇입니까?

우리는 대O, 대Omega와 유사한 대Theta의 조건산을 생각할 수 있다.

대 O는 <=와 유사하고 알고리즘의 성장률이 특정 값보다 작거나 같다는 것을 의미한다. 예를 들어 f(x)

대ω는 >=와 유사하며 성장률이 지정한 값보다 크거나 같다는 것을 의미한다. 예를 들어 f(x)>=Ω(n).

대 θ는 ==와 유사하며 성장률이 지정한 값과 같다는 것을 의미한다. 예를 들어 f(x) =Θ(n^2).

그러나 만약에 우리가 모든 상황에 대해 전면적인 진술을 해야 한다면, 우리는 큰 O를 사용할 것이다. 예를 들어 삽입 정렬이 O(n^2)라고 가정할 것이다.

최적 상황, 최악 상황 및 예상 상황

최적 상황/최악 상황/예상 상황과 대O/Big Omega/Big Theta 간의 관계는 무엇입니까?
하나도 없어요.
일반적으로 큰 O와 최악의 상황, 큰 Omega와 최상의 상황, 큰 Theta와 평균 상황 사이에서 등가를 진행하지만, 우리는 이 기호 중의 하나하나를 위해 최상, 최악과 평균을 이야기할 수 있다.
예를 들어, 다음 각 진술은 정확합니다.

삽입 정렬의 최악의 경우 증가율은 O(n^2)

로 가장 높다

삽입 정렬의 최악의 경우 증가율은 최소 Ω(n)

삽입 정렬의 최악의 경우 성장률은Θ(n^2)

대오, 대오메가, 대오메가, 대탄식!

이 강좌에서 당신은 대O, 대오메가와 대오메가 기호 간의 차이를 배웠습니다.
우리 안에 있고 싶어요?나는 매주 프로그래밍, 문제 해결, 평생 공부에 관한 시사 통신을 쓴다.Sign up for The Solution