네, 반갑습니다. 오늘 이 영상을 끝까지 보신 후엔 시간 복잡도의 개념을 알게 되고 여러 예제를 통해서 시간 복잡도를 표현하는 방법을 이해하게 됩니다.

자, 그럼 오늘도 시간 복잡도, 영어로는 타임 컴플렉시티(Time Complexity) 라고 하는데요.

요거 한번 살펴볼게요. 자, 여기 이렇게 코드가 하나 있습니다.

이 코드는 어떤 코드냐면 이렇게 배열을 파라미터로 받고 또 멀티플라이어(multiplier)를 파라미터로 받습니다.

그럼 얘는 어떻게 동작하냐면 여기에 이 배열로 전달받은 그 크기만큼의 새로운 배열을 하나 만들고요.

그 다음에 기존에 전달받은 그 배열 크기만큼 이렇게 루프를 돌면서 그 배열에 있는 값을 파라미터로 전달받은 멀티플라이어와 곱해서 그 곱한 값을 새로운 배열에 저장하는 코드입니다.

그렇게 해서 최종적으로 새로운 배열을 이렇게 리턴을 하게 되는 거죠.

그러면 이제부터 우리가 할 것은 뭐냐면 이 함수를 실행했을 때 이 함수의 실행 시간이 어느 정도였지 한번 표현을 해보고 싶은 거죠.

근데 여기서 실행 시간이라는 것이 사실은 컴퓨터에서 동작한다고 했을 때 컴퓨터 성능에 따라서 다 조금씩 다를 거잖아요.

그래서 이걸 좀 더 간단하게 계산하기 위해서 어떻게 하냐면 이 실행 시간 이라는 개념을 함수나 혹은 알고리즘 수행에 필요한 스텝스라고 이제 표현합니다.

그러니까 어떤 뭐 밀리 세컨드, 세컨드 이런 개념이 아니라 이 함수나 알고리즘을 수행하기 위해 필요한 스텝스를 실행 시간이라고 이렇게 정의를 해보자는 거죠.

그래서 이렇게 정의를 하고 추가적으로 좀 더 간단하게 계산을 하기 위해서 이 각각의 라인들 있잖아요.

이 각 라인을 수행하기 위해 필요한 스텝스는 상수, 그러니까 고정된 값이라고 가정을 해 보자는 거죠.

그러면 이런 가정들을 가지고 수식을 세워 보도록 할게요.

지금 보시면 이렇게 각 라인별로 몇 개의 스텝이 필요한지를 표현했습니다.

이 각각 이제 상수인 거죠. 각 라인을 실행할 때마다 이 정도의 스텝이 필요하다 이렇게 상수로 표현을 해 놓았고요.

그러면 이제 각각의 이 라인이 몇 번씩 실행된다 요게 더 중요한 거죠.

그러면 이 라인 같은 경우에는 한 번만 실행을 할 거고요.

이 라인 같은 경우에는 이 배열의 사이즈가 만약에 n이라고 했을 때 n+1번에 실행이 될 겁니다.

여기에 1번이 더 추가가 된 이유는 얘가 루프를 돌고 최종적으로 루프를 탈출하기 위한 검사를 한 번 더 하기 때문에 플러스 1이라고 한 거고요.

그다음 a4 루프 안에 있는 요 라인은 이제 n번이 실행이 되겠죠.

그리고 마지막 요 라인은 또 한 번 실행이 될 겁니다.

그렇게 최종적으로 이제 얘가 어떻게 계산이 될 거냐 하면은 각각의 코스트와 이 코스트를 가지는 한 라인이 몇 번씩 실행되는지를 곱해서 이렇게 곱한 다음에 그렇게 곱한 값들을 다 더해 줘야 되겠죠.

이런 식으로 다 더 해줘야 될 겁니다.

그렇게 했을 때 이 수식을 정리하면 어떻게 되냐 하면 이런 식으로 수식이 정리가 될 겁니다.

여기서 이제 Tn이라는 것은 실행 시간을 n이라는 파라미터, 즉 여기 이 배열 인풋 사이즈의 크기를 말하는 거죠.

인풋 사이즈에 따라서 이 실행 시간이 영향을 받을 거라서 Tn이라고 표시를 했고요. 그래서 아까 그 수식을 이런 식으로 깔끔하게 정리를 하면 최종적으로는 이런 형태가 나오게 됩니다.

여기서 이제 A에 해당하는 부분이 C2 플러스 C3가 될 거고 그다음에 B에 해당하는 부분이 C1 플러스 C2 플러스 1 이 부분이 될 겁니다.

그래서 식을 간단하게 해주기 위해서 이렇게 치환을 해 준 거예요.

이렇게 해서 최종적으로 이 실행 시간은 An 플러스 B가 된 거고 여기서 n은 인풋 사이즈인 건데 지금 이 상황에서 이 이상으로 더 정확한 계산을 하기는 조금 어렵습니다.

그리고 또 여기서 주목해 볼 만한 부분은 뭐냐면 인풋 사이즈의 n이 작을 때는 실행 시간이 크게 의미가 없죠.

이 배열의 크기가 작다면 실행 시간은 뭐 금방 끝날 테니깐요. 그래서 사실 우리가 정말 궁금해할 만한 부분은 n이 점점 증가해서 무한대로 향해 갈 때, 그러니까 이 인풋 사이즈가 계속 증가할 때 이때의 실행 시간이 어떻게 될지가 궁금한 겁니다.

그러면 인풋 사이즈 n이 점점 무한대로 갈 때 우리는 어떻게 처리를 해줄 수 있느냐?

n이 커질수록 일단 덜 중요한 것은 제거를 할 수 있습니다.

무슨 말이냐면 이 최고차항만 일단 의미가 있어요.

오른쪽에 보시면 여기서 최고차항은 이 부분이죠. 그러면은 이 뒤 부분, 요 부분 의미가 없다는 겁니다.

요 최고차항만 의미가 여기서 최고차항이라는 것은 이 실행 시간 함수가 인풋 사이즈 n에 대한 함수이기 때문에 n에 대한 최고차항이 의미가 있다라는 그런 뜻이고요.

그래서 지금 이 항이 최고차항이기 때문에 이 부분 빼고는 다 의미가 없게 되는 겁니다.

그리고 또 최고차항에서도 계수는 의미가 없다.

여기서 계수라는 것은 이제 이 부분이죠.

이 부분은 의미가 없다. 그렇게 했을 때 최종적으로 이 실행 시간을 어떻게 표현할 수 있냐면 이렇게 표현할 수 있습니다.

예를 일단 읽는 방법은 세타 O(N) 혹은 빅 세타 O(N)이라고 읽을 수 있고 저는 이제 편하게 읽으려 그냥 세타라고 읽는데요.

어쨌든 여기서 이제 앞에 보이는 이 기호 있잖아요.

이 기호는 조금 있다가 설명드릴게요. 그래서 다시 한번 정리하면 이렇게 N이 무한대로 갈 때, 인풋 사이즈가 계속 커질 때 이 함수의 실행 시간은 어떻게 표현할 수 있냐?

이렇게 표현할 수 있다는 겁니다.

자 그러면 N 인풋 사이즈가 무한대로 갈 때, N 인풋 사이즈가 커질수록 덜 중요한 것은 제거하는 이런 접근법.

그래서 최고 차항만 남겨두고 또 최고 차항의 계수는 의미가 없기 때문에 그 계수는 제거하는 이런 방식, 이런 분석 방식을 뭐라고 하냐면 점근적 분석이라고 합니다.

영어로는 Asymptotic Analysis라고 하는데요.

아까 앞에서 보셨던 것처럼 n으로 표현되는 의미에 함수가 그 해님 원 들어갈 때 이 이미 함수는 어떤 함수 형태에 근접해 지는지 분석하는 것을 점근적 분석이라고 하고요 오른쪽에서 이렇게 세타 n으로 표기하는 이런 표기법을 뭐라고 하냐면 점근적 표기법이라고 합니다.

요건 뒤에 다시 한번 설명을 할 거예요.

자, 그럼 정리를 하겠습니다. 시간 복잡도라는 것은 함수의 실행 시간을 표현하는 것을 의미를 해요.

그런데 이때 어떻게 표현을 하냐면 주로 점근적 분석을 통해서 실행 시간을 단순하게 표현하고요.

이때 요 어떤 표기법으로 표현하려면 점근적 표기법을 통해서 표현합니다.

그래서 시간 복잡도라는 것은 함수의 실행 시간을 점근적 분석을 통해서 점근적 표기법으로 표현하는 것을 시간 복잡도라고 한다.

그렇게 이해를 하시면 될 것 같습니다. 자, 그래서 다시 처음 코드로 돌아와서 우리가 방금 살펴보았던 요 개념으로 이 함수의 시간 복잡도를 표현을 하면 바로 O(N)이 된다.

이렇게 이해하시면 되겠습니다.

그럼 이제 점근적 표기법을 한번 살펴볼게요. 자, 여기 새로운 코드가 있습니다.

이건 아까와는 다른 코드인데요. 얘는 어떤 기능을 하는 함수 냐면 여기 정수 배열로 인풋을 받습니다.

그리고 거기에 타겟을 파라미터로 또 전달받아요.

얘는 어떤 거냐면 이 배열에 이 찾으려는 타겟이 있는지 없는지를 확인해서 있으면 true, 없으면 false를 리턴하는 그런 함수입니다.

그래서 코드를 보시면 여기서 루프를 통해서 이 배열에 있는 인풋 데이터들을 다 하나씩 확인해요.

그래서 찾으려는 타겟과 같으면 이렇게 true를 바로 리턴한 뒤 함수를 종료시키는 거구요.

끝까지 다 갔는데도 찾는 타겟이 없었다면 최종적으로 false를 리턴을 하게 되는 겁니다.

이해가 되시죠? 자, 그러면 이제 이 함수의 시간 복잡도를 구해보도록 하겠습니다.

그런데 문제는 여기서 시간 복잡도를 구해 보려고 하니까 이 함수의 파라미터 데이터에 따라서 실행 시간이 조금씩 다를 것 같아요.

왜냐하면 예를 들어서 이런 인풋이 있다고 해 보겠습니다.

여기 배열이 이렇게 있는데 이 배열에서 만약에 찾으려는 숫자가 이 앞쪽에 있으면 이 함수의 실행 시간은 빨리 끝날 거고, 반면에 찾으려는 숫자가 이 뒤쪽에 있으면 이 함수의 실행 시간은 오래 걸릴 거 잖아요.

그래서 이 함수에 파라미터 데이터에 따라서 실행 시간이 조금씩 다를 수가 있다는 거죠.

그러면 이런 경우에는 케이스에 따라서 분류를 해서 확인해 보는 게 좋은데요.

이런 식으로 케이스를 한번 분류해 봤습니다.

베스트 케이스는 뭐냐면 찾으려는 숫자가 그 배열의 0번째 존재를 하는 거죠.

그러니까 요 위치에 존재를 하는 겁니다. 이때는 완전 베스트, 이때는 딱 한 번 확인하고 끝나게 되는 거니까요.

근데 반면에 최악의 케이스, 워스트 케이스는 뭐냐면 찾으려고 하는 숫자가 맨 마지막에 있거나 아니면 아예 이 배열에는 존재하지 않는 경우에 이 때를 최악의 경우라고 볼 수 있습니다.

이 배열의 사이즈가 N 이라고 했을 때 N번을 확인을 해 줘야 되기 때문에 이 케이스를 최악의 케이스, 그러니까 워스트 케이스가 되는 거죠.

그러면 이 경우를 가지고 이 함수의 실행 시간을 어떻게 문장으로 표현해 볼 수 있을까요?

이렇게 표현해 볼 수 있을 것 같습니다.

먼저 이 하한선을 기준으로 설명을 해보면 이 함수의 실행 시간은 아무리 빨라도 상수 시간 이상입니다.

그러니까 이 바로 무슨 말이냐면 가장 빨리 찾을 때는 뭐 한 번 만에 찾든 두 번 만에 찾든 앞쪽에 있으니까 빨리 찾을 거잖아요.

그러면은 이건 인풋 사이즈와는 상관없이 대단히 빨리 찾게 되는 이 케이스가 있는 거라서 그러면 이 함수의 실행 시간은 하한선을 가지고 표현했을 때 아무리 빨라도 상수 시간 이상이다 이렇게 표현을 할 수 있을 거고요.

반면에 상한선 그러니까 어퍼 바운드를 기준으로 설명을 하게 되며 이 함수의 실행 시간은 아무리 오래 걸려도 인풋 사이즈 n에 비례하는 정도를 넘어서지 않는다, 그 이하다 이렇게 설명을 할 수 있을 겁니다.

그러니까 이 함수의 실행 시간을 표현하는 방법은 하한선 기준으로 설명할 수도 있고 상한선 기준으로 설명할 수 있는 겁니다.

즉 아무리 빨라도 이 정도는 걸린다 이렇게 표현할 수도 있고 반대로 아무리 오래 걸려도 이 정도를 넘어 서지 않는다 이렇게 표현할 수 있는 거죠.

그러면 방금 이렇게 문장으로 하 한선 기준으로 이 함수의 실행 시간을 표현하는 것과 또 상한선을 기준으로 함수의 실행 시간을 표현하는 것을 문장이 아니라 점근적 표기법으로 표현하면 어떻게 되냐면 이렇게 표현할 수 있습니다.

얘는 저는 편의상 빅 오메가 n이라고 읽을 거고요 그리고 얘는 편의상 빅 오 n이라고 읽겠습니다.

그럼 여기서 이 빅 오메가 가 의미하는 것은 로워 바운드 하한을 의미하는 거고요.

그리고 여기서 빅 오가 의미하는 것은 어퍼 바운드 상한을 의미하는 겁니다.

그리고 이 안의 숫자 1로 표현되는 것은 얘는 상수 시간이 걸린다.

그러니까 인풋 사이즈에 상관없이 얘는 상수 시간으로 아주 빨리 처리가 된다 이런 의미고요.

여기서 n이 의미하는 것은 인풋 사이즈 n에 비례하는 함수 형태를 띤다 그렇게 이해를 하시면 되겠습니다.

그래서 이 함수의 실행 시간을 표현할 때는 이렇게 해서 표현해 줄 수도 있고 혹은 이렇게 표현해 줄 수도 있어요.

둘 다 맞는 표현인데 보통 우리가 워스트 케이스를 더 의미있게 보기 때문에 이렇게는 잘 표현하지 않고요.

이 빅 오 노테이션을 써서 많이 표현을 한다 그렇게 이해를 하시면 될 거 같습니다.

자 그러면 이번에는 같은 코드를 케이스별로 시간 복잡도를 구해 보겠습니다.

자 여기 베스트 케이스가 있고 워스트 케이스가 있어요. 그리고 [음악] 우리가 바로 앞에서 빅 오메가 노테이션과 빅 오 노테이션을 배웠습니다.

그리고 여기 빅 세타. 저는 편의상 그냥 세타로 갈게요. 이 세타 노테이션 은 이제 곧 설명을 드릴게요.

자, 그럼 베스트 케이스는 뭐냐? 아까 앞에서도 설명드렸던 것처럼 바로 첫 번째 찾으려는 데이터가 있는 경우겠죠.

그럼 이 경우에는 로우 바운드로 표현을 하든 어퍼 바운드로 표현을 하든 둘 다 상수 시간에 끝나게 됩니다.

왜냐하면 이 첫 번째 위치에 바로 찾았으니까 얘가 로우 바운드, 어퍼 바운드는 무조건 상수 시간에 끝나는 거죠.

그러면은 이 두 개는 이렇게 표기할 수 있습니다. 자, 이런 식으로 이렇게 표기를 할 수 있어요.

시간복잡도(time complexity)를 알차게 설명합니다! 빅 오(Big O)를 포함해서 점근적 표기법을 다양한 예제와 함께 설명하니까요 들러보세요~ :)

8년차 백엔드 개발자가 배워서 남주려고 만든 채널이에요

알기 쉽게 설명합니다

함께 성장했으면 좋겠어요 :)


#컴공맛집 #백엔드전문채널


쉬운코드

시간 복잡도는 함수의 실행 시간을 점근적 분석을 통해 점근적 표기법으로 단순하게 표현하는 것을 의미합니다.

점근적 표기법에는 최악의 경우(상한선)를 나타내는 빅 O (O), 최선의 경우(하한선)를 나타내는 빅 오메가 (Ω), 그리고 상한선과 하한선이 같은 경우(타이트 바운드)를 나타내는 빅 세타 (Θ) 세 가지가 있습니다.

시간 복잡도의 성능은 O(1) (상수 시간)이 가장 빠르며, O(log n), O(n), O(n log n), O(n^2), O(2^n), O(n!) 순으로 느려집니다.

시간 복잡도(Time Complexity)는 **함수나 알고리즘의 실행 시간을 표현하는 개념**입니다. 이는 컴퓨터 성능에 따라 달라질 수 있는 실제 시간(밀리초, 초 등) 대신, 알고리즘 수행에 필요한 '스텝'의 수로 정의됩니다. 각 코드 라인 실행에 필요한 스텝은 상수 값으로 가정하여 계산하며, 전체 실행 시간은 각 라인의 스텝 수와 실행 횟수를 곱한 뒤 모두 더한 값으로 표현됩니다.

예를 들어, 배열의 크기(N)에 비례하여 루프가 도는 코드의 실행 시간은 N에 대한 함수 `Tn = AN + B` 형태로 나타낼 수 있습니다. 여기서 N은 입력 배열의 크기를 의미합니다. 그러나 작은 N 값에서는 실행 시간이 크게 중요하지 않으므로, **N이 무한대로 증가할 때의 실행 시간 변화에 주목**합니다.

N이 커질수록 덜 중요한 항은 제거하고, 최고차항만 남깁니다. 또한 최고차항의 계수도 의미가 없으므로 제거하는데, 이를 **점근적 분석(Asymptotic Analysis)**이라고 합니다. 이 분석을 통해 함수의 실행 시간을 `O(N)`과 같은 형태로 단순하게 표현하며, 이러한 표기법을 점근적 표기법이라고 합니다.

점근적 표기법: 빅 오메가, 빅 오, 세타

함수의 실행 시간은 입력 데이터의 특성에 따라 달라질 수 있으므로, **최적(Best Case), 최악(Worst Case), 평균(Average Case)의 세 가지 케이스로 분류**하여 분석합니다. 이때 실행 시간의 하한선(Lower Bound)과 상한선(Upper Bound)을 나타내는 점근적 표기법을 사용합니다.

**빅 오메가(Ω)는 하한선(Lower Bound)을 의미**하며, 아무리 빨라도 이 정도 시간 이상은 걸린다는 것을 나타냅니다. 예를 들어, 배열의 첫 번째 요소에서 값을 찾는 베스트 케이스의 경우, 실행 시간은 상수 시간(`Ω(1)`) 이상으로 표현됩니다.

**빅 오(O)는 상한선(Upper Bound)을 의미**하며, 아무리 오래 걸려도 이 정도 시간 이하로 끝난다는 것을 나타냅니다. 배열 전체를 탐색해야 하는 최악의 경우, 실행 시간은 입력 크기 N에 비례하는 `O(N)` 이하로 표현될 수 있습니다.

**세타(Θ)는 타이트 바운드(Tight Bound)를 의미**하며, 하한선과 상한선이 동일할 때 사용됩니다. 이는 최솟값과 최댓값이 같아서, 함수의 실행 시간이 특정 함수 형태에 아주 가깝게 수렴함을 나타냅니다. 예를 들어, 베스트 케이스나 워스트 케이스 모두 실행 시간이 상수이거나 N에 비례하는 경우, `Θ(1)` 또는 `Θ(N)`으로 표현할 수 있습니다.

평균 케이스(Average Case)는 일반적으로 워스트 케이스와 유사하게 `O(N)`과 같이 빅 오 표기법으로 표현되는 경우가 많습니다. 이는 평균적인 상황에서 상한선만을 명확히 제시하는 방식으로, 로워 바운드나 타이트 바운드를 정의하기 모호할 때 주로 사용됩니다.

앞서 다뤘던 배열의 각 요소에 `multiplier`를 곱하는 함수는 **입력 사이즈 N에 비례하는 `Θ(N)`의 시간 복잡도**를 가집니다. 이는 베스트, 워스트, 평균 케이스 모두 N에 비례하는 시간이 걸리기 때문입니다.

정렬된 배열에서 특정 값을 찾는 **이진 탐색(Binary Search)의 최악 케이스 시간 복잡도는 `Θ(log N)`** 입니다. 이는 탐색 범위가 매번 절반으로 줄어들기 때문입니다. 베스트 케이스는 첫 시도에 값을 찾는 경우이므로 `Θ(1)`입니다.

중첩된 루프를 사용하는 함수는 입력 크기 N에 대해 **`Θ(N^2)`의 시간 복잡도**를 가집니다. 바깥 루프가 N번, 안쪽 루프가 N번 실행되기 때문입니다.

두 개의 독립적인 루프가 각각 다른 입력 크기 N과 M에 대해 실행되는 경우, 시간 복잡도는 **두 입력 중 더 큰 값에 영향을 받는 `Θ(max(N, M))` 또는 `Θ(N+M)`** 이 됩니다.

두 개의 입력 N과 M에 대해 중첩된 루프가 실행될 경우, 시간 복잡도는 **`Θ(N*M)`** 이 됩니다.

시간 복잡도 성능 비교 및 빅 오 표기법 선호 이유

알고리즘의 성능은 일반적으로 **`O(1)` (상수 시간) > `O(log N)` > `O(N)` > `O(N log N)` > `O(N^2)` > `O(2^N)` > `O(N!)` 순으로 우수**합니다. 오른쪽으로 갈수록 실행 시간이 길어지고 성능이 저하됩니다.

면접이나 코딩 테스트 등에서 **빅 오(Big O) 표기법이 가장 흔하게 사용되는 이유**는 다음과 같습니다:

첫째, **일반적으로 어퍼 바운드(상한선)만 알아도 충분**하기 때문입니다. 사람들은 최악의 상황을 가정하고 계획을 세우는 경향이 있어, 알고리즘의 최대 실행 시간을 아는 것이 실용적입니다.

둘째, **다른 바운드를 계산하는 것이 번거롭거나 까다로울 수 있기 때문**입니다. 이미 상한선을 구했다면 굳이 더 복잡한 계산을 하려 하지 않습니다.

셋째, **타이트 바운드로 표현했다가 논란의 여지를 만들고 싶지 않기 때문**입니다. 특히 평균 케이스의 경우 세타 표기법으로 정확하게 표현하기 어려울 수 있으므로, 확실한 어퍼 바운드인 빅 오를 선호합니다.

넷째, **다수가 빅 오를 사용하기 때문**에 관습적으로 따르는 경향이 있습니다. 마지막으로는 점근적 표기법의 개념을 잘 알지 못해 무조건 빅 오를 사용하는 경우도 있습니다.

결론적으로, **세타를 사용해야 하는 상황에서 빅 오를 사용해도 틀린 것은 아니며**, 개념을 정확히 이해하고 있다면 대부분의 상황에서 빅 오 표기법을 주로 사용하게 됩니다.

시간 복잡도를 계산할 때 함수의 실행 시간을 '스텝스'로 정의하고 각 라인 수행에 필요한 스텝스를 상수로 가정하는 이유는 무엇인가요?

점근적 분석에서 N이 무한대로 향할 때 실행 시간을 단순화하기 위해 덜 중요한 요소를 제거하는 과정과 그 이유에 대해 설명해 주세요.

빅 오메가(Ω), 빅 오(O), 빅 세타(Θ) 표기법 각각이 무엇을 의미하며, 특정 케이스(베스트, 워스트, 에버리지)에서 이들을 어떻게 활용하여 시간 복잡도를 표현할 수 있는지 궁금합니다.

바이너리 서치 알고리즘의 워스트 케이스 시간 복잡도가 O(log n)이 되는 과정을 예시를 통해 자세히 설명해 주세요.

일반적으로 빅 오(Big O) 표기법이 가장 많이 사용되는 이유가 무엇이며, 다른 점근적 표기법에 비해 어떤 장단점이 있나요?

시간 복잡도 개념 소개 및 예제를 통한 이해

배열과 멀티플라이어를 파라미터로 받는 코드 설명

새로운 배열 생성 및 루프를 통한 값 계산

멀티플라이어와의 곱 연산 및 새로운 배열에 저장

함수 실행 시간 표현의 필요성 강조

실행 시간 계산 및 점근적 분석 소개

컴퓨터 성능에 따른 실행 시간 차이 고려

실행 시간을 알고리즘 수행에 필요한 스텝으로 정의

각 라인의 수행 스텝을 상수로 가정

라인별 스텝 수와 실행 횟수 계산

수식 정리 및 실행 시간(tn)과 입력 사이즈(n)의 관계 설명

점근적 분석 방법 및 시간 복잡도 표기법

입력 사이즈 증가에 따른 실행 시간 변화 분석

덜 중요한 항 제거 및 최고차항의 의미 강조

시간 복잡도 표현 방법(빅 O 표기법 등) 소개

점근적 분석(asymptotic analysis)과 점근적 표기법(asymptotic notation) 설명

시간 복잡도의 정의 및 점근적 분석과 표기법의 관계 정리

다른 코드 예시 및 케이스별 시간 복잡도 분석

타겟 검색 함수 코드 설명 및 시간 복잡도 분석의 어려움

케이스별(베스트, 최악) 실행 시간 차이 분석

하한선(lower bound)과 상한선(upper bound) 기준으로 실행 시간 표현

문장으로 표현된 실행 시간을 점근적 표기법으로 표현

케이스별(베스트, 최악) 시간 복잡도 비교 및 빅 오메가, 빅 오, 빅 세타 노테이션 설명

점근적 표기법 정리 및 케이스별 시간 복잡도 분석

빅 오메가, 빅 오, 빅 세타 노테이션의 의미 정리

케이스별(베스트, 최악, 평균) 시간 복잡도 분석 방법 설명

케이스별 적절한 표기법 사용의 중요성 강조

이전 코드의 시간 복잡도가 세타 n인 이유 설명

바이너리 서치의 시간 복잡도 분석

바이너리 서치 개념 및 시간 복잡도 분석

최악의 경우(워스트 케이스) 분석 및 실행 과정 설명

매번 실행 시 사이즈가 절반으로 줄어드는 점 강조

워스트 케이스 시간 복잡도를 점근적 표기법으로 표현(세타 로그 n)

최상의 경우(베스트 케이스) 시간 복잡도 분석(세타 1)

추가 예제를 통한 시간 복잡도 분석

이중 루프를 사용하는 함수의 시간 복잡도 분석(세타 n 제곱)

두 배열을 입력으로 받는 함수의 시간 복잡도 분석(세타(max(n, m)))

이중 루프를 사용하는 함수의 시간 복잡도 분석(세타(n * m))

시간 복잡도 비교 및 빅 O 표기법 사용 이유

다양한 시간 복잡도(O(1), O(log n), O(n), O(n log n), O(n^2), O(n!)) 비교

빅 O 표기법을 주로 사용하는 이유(최악의 경우 고려, 계산 편의성 등)

빅 O 표기법 사용의 재미있는 이유(키보드에 오메가와 세타가 없다는 댓글 언급)

시간복잡도(time complexity)를 알차게 설명합니다! 빅 오(Big O)를 포함해서 점근적 표기법을 다양한 예제와 함께 설명하니까요 들러보세요~ :)

스크립트