무향향수

시간 복잡도(Time Complexity)알고리즘의 효율성을 평가하는 기준을 말한다.알고리즘이 실행되는 데 걸리는 시간을 입력 크기 n에 따라 나타낸 것이다.기본적인 시간 복잡도 종류O(1) - 상수 시간 (Constant Time)입력의 크기와 관계없이 일정한 시간이 걸리는 알고리즘O(n) - 선형 시간 (Linear Time)입력의 크기 n에 비례하여 시간이 걸리는 알고리즘O(n^2) - 이차 시간 (Quadratic Time)입력 크기의 제곱에 비례하여 시간이 걸리는 알고리즘O(log n) - 로그 시간 (Logarithmic Time)입력 크기가 커질수록 실행 시간이 느리게 증가하는 알고리즘O(n log n) - 선형 로그 시간 (Linearithmic Time)선형 시간과 로그 시간이 결합된 알..

더보기처음 파이썬으로 문제를 풀었을 때 채점 시간이 엄청 오래 걸리더니 결국 시간초과가 나버렸다. 언제나처럼 이중 for문을 사용한 것이 문제였고 문제를 해결한 다른 블로그를 참조하여 코드를 작성하였다. 이중 for문이 쉽고 좋은데.. 시간이 너무 오래 걸려서 슬프다. 이전까지는 이중 for문이 만능이었는데 시간복잡도나 자료구조, 알고리즘을 배우고 코드를 작성해보니 최악이라는 생각이 들기도 한다. 더 열심히 대응방안을 찾아봐야겠다.   처음에 작성했던 코드 (시간 초과)import sysN = int(sys.stdin.readline()) # 수 입력받기a = [2]for i in range(N, 1000000000000): # while문 대신 for문을 사용 x = 1 for j i..

알고리즘에서 시간 복잡도는 주어진 문제를 해결하기 위한 연산 횟수를 말한다.일반적으로 수행 시간은 1억번의 연산을 1초의 시간으로 간주어 예측한다. 빅-오메가: 최선일 때의 연산 횟수를 나타낸 표기법빅-세타: 보통일 때의 연산 횟수를 나타낸 표기빅-오: 최악일 때의 연산 횟수를 나타낸 표기법 코딩테스트에서는 빅-오 표기법을 기준으로 수행시간을 계산하는 것이 좋다.   연산 횟수 = 알고리즘 시간 복잡도 * 데이터의 크기 1. 상수는 시간 복잡도 계산에서 제외한다.2. 가장 많이 중첩된 반복문의 수행 횟수가 시간 복잡도의 기준이 된다.