inputs를 받는 함수가 있다고해보자 inputs의 길이만큼 loop 돌고 그 안에 또 2중으로 for문이 돌아간다 .
이럴경우
N * N = N제곱 이라고 할수있을것이다.
결국 이 함수의 시간 복잡도는
라고 표현 할 수 있다.
다음 예제이다
이 함수는 두개의 배열을 인자로 받는다.
이 경우에는 동등한 위치에서 for loop가 동작하는걸 알수 있 다.
한번은 inputsA 의 배열만큼 돌고 이게 끝이나면 inputB 배열의 사이즈만큼 loop가 돈다
이럴경우 시간 복잡도는
이렇게 표기할수있다.
이때 N은 inputA의 사이즈라 하고 M이 inputB의 사이즈라고 정하겠다.
결국 이 시간복잡도는 결국 둘중 하나가 큰값인 것에 영향을 받을것이다
이 경우에는 N,M 중 MAX 값이 시간 복잡도에 영향이 갈것이다 결국 표현하자면
이렇게 표기할수 있지만 위에 먼저 표기한것과 같다.
마지막 예제를 한번 봐보자
각각 input 값이 다른 a,b를 인자로 받아오고 있고 2중 for문이 돌고 있다.
밖에서는 input A사이즈 만큼 루프가 돌고있고 그 안에서는 input B의 사이즈만큼 돌고있다.
이런 경우에는 어떻게 시간복잡도로 표현을 해야하는가?
이렇게 표기하면 된다.
A가 => N
B가 => M
일 경우 이중 for문을 사용한다면 이렇게 표현한다고 한다.
시간복잡도 속도 비교
오른쪽으로 갈수록 속도와 성능이 저하된다.
이 글은 youtube 강의를 보고 정리했다.
https://www.youtube.com/watch?v=tTFoClBZutw&t=968s
수정사항 youtube 댓글참조
- Θ(1) == O(1)??
- 알고리즘이나 함수의 실행 시간을 표현할 때는 Θ(1) == O(1) 는 true입니다.
- 하지만 일반적인 수학의 세계에서는 Θ(1) == O(1)는 false 입니다.
-
merge sort의 시간복잡도는 O(NlogN)으로 많이들 표현하지만 보다 정확한 표현은 Θ(NlogN) 입니다
-
Θ, O, Ω 개념을 완전 FM대로 설명하려면 영상에서 다뤘던 수준보다 더 디테일하게 수학적으로 다뤄야 합니다만 그러면 내용이 더 어려워지고, (그렇게까지 디테일하게 몰라도) 영상에서 다룬 정도로만 이해하고 있으면 무리 없이 읽고 또 대화할 수 있기 때문에, 걱정 없이 영상을 보고 즐기시면 되겠습니다 :)
-
2.36에서 T(N) 수식의 첫 줄의 맨 마지막은 1이 아니라 c4가 되어야 합니다ㅜㅠ 오타가 있었네요 죄송합니다 ㅠㅠ (시간복잡도 계산하는 부분에서는 어차피 상수라 마지막에 b로 함께 묶이게 되는 것은 동일합니다)
