Time Complexity 썸네일형 리스트형 코딩테스트에서 요구되는 시간복잡도 어림잡기 온라인 코딩 테스트에서는 제한시간내에 문제의 따른 정확한 값을 반환하는 프로그램을 작성해야한다. 제한시간내에 동작하는 프로그램을 작성하기 위해서 어떻게 해야할까? 컴파일러, 각 컴퓨터의 프로세서의 차이 등이 실행시간에 영향을 끼치겠지만, 컴퓨터는 평균적으로 10**8개의 연산을 1초이내에 수행할 수 있다. 이를 기준으로 시간제한과 주어진 데이터 크기 제한에 따른 시간복잡도를 예측하고 그것에 맞게 답안을 작성하는 편이 더 빠른 솔루션이 있지않을까 고민하는 것 보다 효율적이다. 데이터 크기 제한 예상되는 시간 복잡도 n 더보기 Asymptotic analysis, 점근적 표기법. 알고리즘의 성능을 분석하기위해 점근적 표기법을 이용해 시간복잡도 사용한다. 단순히 특정 입력 값에 따른 실행시간(running time)을 비교하는게 아니라, 입력값이 증가함에 따른 Running time의 rate of growth를 표현한 것이 시간 복잡도(time complexity)이다. Big-theta Running time에 대한 점근적인 한계값을 Big theta라 한다. 즉, 알고리즘의 평균 시간복잡도를 말한다. Big-O 빅오는 running time에 대한 점근적인 상한값을 말한다. 즉, 알고리즘의 최악의 시간 복잡도이다. 보편적으로 ‘시간 복잡도’는 최악의 케이스를 커버하능 빅오를 말한다. Big-omega 빅 오메가는 running time에 대한 점근적인 하한값을 말한다.. 더보기 이전 1 다음
