[algorithm] 시간 복잡도에 대하여(1)

Before we start...

 

백준 11단계를 푸는중에 문제 자체가 이해가 되지 않았다.

 

11단계에 대해서 구글링해본 결과

 

시간 복잡도에 대한 이해도가 있어야 풀 수 있는 문제라고 한다.

 

그렇다 많이 들어봤지만 정확하게 알지 못하는 개념 

 

시 간 복 잡 도...

 

오늘은 그 개념에 대해서 심층적으로 알아볼 생각이다.

 

우선 시간복잡도에 대해서 알아보기 전에 알고가야하는 부분이 있다.

 

알고가자

 

컴퓨터 즉, 알고리즘 세계에서는

 

속도가 빠르다를 인간세계 처럼 "초" 단위로 표현하지 않는다.

 

같은 알고리즘이라도 컴퓨터 사양(하드웨어)에 따라

 

실행 속도는 현저히 다르기 때문...

 

따라서 알고리즘의 속도는 

 

"완료까지 걸리는 절차의 수" 로 결정이 된다.

즉, 5개의 절차의 수를 가진 알고리즘 > 10개의 절차의 수를 가진 알고리즘 

 

이렇게 5개의 절차의 수를 가진 알고리즘이 10개의 절차의 수를 가진 알고리즘보다 속도가 빠르다고 할 수 있다.

 

What is Time complexity(시간 복잡도)?

 

왜 시간 복잡도를 사용하나요? Why we must use Time complexity?

 

'함수의 실행 시간을 표현하는 것'

 

주로 점근적 분석을 통해

 

실행 시간을 단순하게 표현하며

 

이 때 점근적 표기법으로 표현함.

 

 

위에서 설명했듯이 실행 시간은

 

우리 인간의 시간대로 표현하기에는 제약이 있다.

 

하드웨어의 차이가 존재하기 때문

 

따라서 점근적 표기법으로 표현한다는 것.

 

시간 복잡도 예제1

 

function multiply(inputs, multiplier) {
    var nums = [];
    for (var i = 0; i < inputs.length; i++) {
        nums.push(inputs[i] * multiplier);
    }
    return nums;
}

 

위의 식을 점근적 분석으로 식을 만들게 된다면

 

아래의 과정을 통해

 

아래의 결과로 도출이 된다.

 

 

a*N + b

 

여기서 a는 c2+c3 이며, b는 c1 + c2 + 1 이다.

 

여기서 N -----> ∞

 

N이 무한일 때

 

• N이 커질수록 덜 중요한 것은 제거.
• 최고차항만 의미가 있다.
• 최고 차항의 계수는 의미가 없다.

 

따라서

 

해당 결과값을 가진다.

 

위의 방식으로 결과값을 도출해나아가는 분석을

 

점근적 분석(Asymptotic analysis) 라고 한다.

 

즉, 점근적 분석이란?

 

임의의 함수가 N -----> ∞ 일 때

 

어떤 함수 형태에 근접해 지는지 분석하는 것.

 

시간 복잡도 예제2

 

function exists(inputs, target) {
    for (let i = 0; i < inputs.length; i++) {
        if (inputs[i] === target) {
            return true;
        }
    }
    return false;
}

 

예제를 살펴보기 전에

 

lower bound(하한선)과 upper bound(상한선)의 개념부터 알고 넘어가는게 좋을 듯 하다.

 

lower bound(하한선) 은 

 

함수 실행 시간이 아무리 빨라도 상수 시간 이상이라는 개념

 

upper bound(상한선) 은

 

함수 실행 시간이 아무리 오래 걸려도 N에 비례하는 정도 이하라는 개념

 

 

위의 문장을 점근적 표기법으로 표현한다면?

 

lower bound(하한선):함수 실행 시간이 아무리 빨라도 상수 시간 이상이라는 개념 ===> Ω(1)

 

upper bound(상한선):함수 실행 시간이 아무리 오래 걸려도 N에 비례하는 정도 이하라는 개념 ===> O(N)

다음 이어지는 내용은 아래 게시글에서...

 

2024.03.05 - [📂 𝐚𝐥𝐠𝐨𝐫𝐢𝐭𝐡𝐦] - [algorithm] 시간 복잡도에 대하여(2)

[algorithm] 시간 복잡도에 대하여(2)

 

 

이 글을 마치며...