컴/알고리즘 (9) 썸네일형 리스트형 시간 복잡도 분석과 알고리즘 정당성 증명 시간 복잡도 가장 널리 사용되는 알고리즘 수행 시간 기준. 알고리즘이 실행되는 동안 수행하는 기본적 연산의 수를 입력의 크기에 대한 함수로 표현한 것 알고리즘의 수행 시간은 반복문이 지배! C++에서 vector, string등의 크기가 큰 구조체를 함수 인자로 넘길 때는 참조형으로 넘기자 (훨씬 빠르게 동작함) 주먹구구 법칙 입력의 크기를 시간 복잡도에 대입해 얻은 반복문 수행 횟수에 대해, 1초 당 반복문 수행 횟수가 1억(10^8)을 넘어가면 시간 제한 초과할 수 가능성 있다 P 문제 : 다항 시간 알고리즘이 존재하는 문제들의 집합 NP 문제 : 답이 주어졌을 때 이것이 정답인지를 다항 시간 내에 확인할 수 있는 문제 ~ 모든 P 문제는 NP 문제에 포함 ex) big-O O(N+P), P < N/.. 이전 1 2 다음