본문 바로가기

이산 수학3

점근 표기법 점근 표기법(Asymptotic Notation) - 어떤 함수가 증가하는 모습을 다른 함수와 비교한다. 알고리즘의 복잡도를 논하거나 단순화시킬 때 사용한다. 빅오 표기법 - 대문자 O를 이용해 표기한다. Order of the function 대략~의 의미이다. 입력 데이터가 증가함에 따라 실행시간 및 공간 복잡도의 증가량을 측정한다. 계수가 없는 단항식으로 표현된다. 1, log n, n, n log n, n^2, n! 순으로 실행 시간이 많이 걸린다. 2023. 1. 29.
도수 분포표 도수 분포표(Frequency Distribution Table) - 특정 구간에 속하는 자료의 개수를 나타내는 표이다. 히스토그램(Histogram) - 도수 분포표를 그래프화 한 것이다. 데이터가 많을 때 가치가 높아진다. 데이터 비닝(Data binning) - 값의 범위에 따라 지정된 통에 데이터를 넣는 것이다. 해시 함수 - 입력값은 임의의 길이를 가질 수 있고, 출력값은 정해진 길이를 가진다. 입력값이 같으면 출력값도 같다. 자료 검색 속도 향상용, 보안, 파일 위변조 검사에 주로 사용된다. 해시 충돌 - 서로 다른 입력값을 해시 함수에 돌렸는데 같은 출력값이 나온 것이다. 근사값 - 근사계산을 통해 얻은 수치로 실제 값에 가까운 값이다. 정확도는 조금 떨어진다. 최적선(Best Fit Lin.. 2023. 1. 29.
조건 명제, 증명 조건 명제(Implication) - p(전제)가 참이면 q(결론)도 참이라고 주장하는 명제이다. 전제와 결론이 존재한다. 전제한 상황이 일어나고(T) 결과가 다를 때만(F) 거짓(F)이다. 전제하지 않은 내용은 무조건 참이다.(무의미한 참 - Vacuous truth) 해당 명제를 다른 조건 명제의 전제로 사용할 수 있기 때문에 반드시 참 또는 거짓이 나와야 한다. 조건 명제에서 전제와 결론의 인과관계는 중요하지 않다. 전제와 결론이 모두 참이어도 인과관계가 성립하지 않을 수도 있다. 공리(Axiom) - 증명 없이 참인 명제이다. 조건 명제의 역(Converse) - p와 q의 위치를 바꾼 것이다. p가 참일 때 q가 참이라고 반드시 q가 참일 때 q가 참이지 않는다. 조건 명제의 이(Inverse).. 2023. 1. 8.