Understanding Time Complexity Through Examples and Notations

시간 복잡도는 Big O와 같은 표기법을 사용한 점근 분석을 통해 함수의 실행 시간을 전달합니다.

### 시간 복잡성 이해하기: 개념 및 예제
* 🕒 이 동영상을 보고 나면 **시간 복잡성의 개념과 다양한 예제**를 통해 이를 표현하는 방법을 이해할 수 있습니다.
* 💻 '시간 복잡도'라는 용어는 알고리즘이 완료되는 데 걸리는 시간을 의미하며, **밀리초나 초 단위가 아닌 단계로 표현**할 수 있습니다.
* 🔄 배열의 각 요소에 승수를 곱하는 주어진 코드에 대해 각 코드 줄의 단계를 계산하여 실행 시간을 분석합니다.
* 📊 실행 시간 공식은 각 라인의 단계 수와 실행 횟수에서 파생되며, **\( O(n) \) 형식의 단순화된 표현**이 됩니다.
* 📈 알고리즘을 분석할 때는 입력 크기가 커질수록 최상위 항에 초점을 맞추기 때문에 **빅오, 빅오메가, 빅세타와 같은 점근 표기법**을 사용하게 됩니다.
* 🔍 예를 들어, 검색 기능에서 **최상의 시나리오는 대상을 즉시 찾을 때** 발생하고, **최악의 시나리오는 대상이 끝에 있거나 전혀 존재하지 않을 때** 발생합니다.
* ⚖ 평균적인 경우 일반적으로 **타겟이 배열의 중간에서 발견**된다고 가정하므로 알고리즘의 성능을 보다 일반화하여 이해할 수 있습니다.
* 📏 궁극적으로 시간 복잡성은 **점근 표기법**을 사용하여 표현되며, 이를 통해 입력 크기에 따라 실행 시간이 어떻게 확장되는지 명확하게 이해할 수 있습니다.

### 빅오 표기법과 시간 복잡도 분석의 이해
* 📚 빅 O 표기법은 알고리즘의 시간 복잡도를 표현하는 데 사용되며, 크게 세 가지 유형으로 분류됩니다: **빅 오메가(Ω), 빅 오(O), 빅 세타(Θ)**.
* 🔍 빅 오메가는 알고리즘 실행 시간의 하한을 나타내고, **빅 O는 상한**을, **빅 세타는 상한과 하한이 모두 수렴하는 타이트한 경계**를 나타냅니다.
* 📊 알고리즘을 분석할 때는 일반적으로 **최상의 경우, 최악의 경우, 평균 시나리오**로 사례를 분류하고 각 사례마다 다양한 조건에서 서로 다른 실행 시간을 반영하는 것이 일반적입니다.
* ⚖ "실제로 가장 좋은 경우는 **알고리즘이 최단 시간 내에 실행되는 경우**"이고, 최악의 경우는 **가장 긴 시간을 의미**하며, 평균적인 경우는 **일반적인 성능**을 반영합니다.
* 📈 예를 들어 이진 검색에서 **최악의 시간 복잡도는 대수(O(로그 n))**이며, **최상의 경우는 대상을 즉시 찾을 때(Ω(1))** 발생합니다.
* 🔄 Big O가 상한값에 자주 사용되지만, 분석하는 사례에 따라 **다른 표기법도 독립적으로 적용**될 수 있다는 점을 이해하는 것이 중요합니다.
* 🔧 이러한 표기법을 철저히 이해하면 알고리즘 성능을 보다 미묘하게 파악할 수 있으므로 개발자는 필요에 따라 **가장 효율적인 접근 방식**을 선택할 수 있습니다.
* 💡 궁극적으로 Big O 표기법이 널리 사용되는 것은 **최악의 시나리오를 추정하는 데 있어 실용적**이기 때문에 알고리즘 성능을 효과적으로 계획하고 최적화하는 데 도움이 되기 때문입니다.

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

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

알기 쉽게 설명합니다

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


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


쉬운코드

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

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

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

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

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

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

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

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

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

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

수식 정리 및 실행 시간(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 표기법 사용의 재미있는 이유(키보드에 오메가와 세타가 없다는 댓글 언급)