시간복잡도

[자료구조]Big-O 표기법

Big-O 표기법 수행시간을 의미하는 T(n)함수값을 결정하는 최고차항만으로 간단하게 표기하는방법 입력값에 대한 증가율을 표기하는것이다.(수행시간이 차이가 있더라도 증가율이 같다면 같은 표기를 한다.) O(최고차항) 최고차항만 남긴다 최고차항 계수(상수)는 생략해준다 Big-O(최고차항)으로 표기한다 상수연산만 하는 알고리즘이라면? def func1(n): return n+1 def func2(n): n += 1 n += 1 n += 1 return n fun1 과 func2 의 T(n)은 각각 1 과 3이다 하지만 두개다 상수이기 때문에 빅오 표기법에서는 아래와 같이 표기한다 O(n**0) = O(1) 증가율이 줄어드는 log의 경우는 어떻게 될까?! def func1(n): count = 0 whil..

[자료구조]시간복잡도(time complexity) - 알고리즘 수행시간

컴퓨터의 HW/SW 환경에 따라 알고리즘의 성능이 달라질 수 있다. (실제로 leet코드에서 문제를 풀고 제출하면 매번 다른 시간이 나온다.) 다양한 크기의 입력이 이루어 지기때문에 알고리즘 별로 크기별 성능 또한 상이 할 수 있다. 이러한 차이때문에 객관적인 평가기준이 그것을 아래와 같은 3가지로 구성하여 측정한다. 가상컴퓨터(Vitual Machine) + 가상언어(Pseudo Langueges) + 가상코드(Pseudo Code) 가상컴퓨터 RAM(Random Accesss Machine) = CPU + memory + 기본연산 으로 구성되어있는 가상의 컴퓨터 기본연산 1단위시간(기본시간)에 수행가능한 연산 배정, 대입, 복사 연산 산술연산 - "+", "-", "*", "/" - 나머지연산, 올림..