전체 글75 Analysis of the Algorithm 3 Worst-Case Complexity Average Complexity - Pr(I): input I가 발생할 확률 - t(I)는 알고리즘 분석으로 결정할 수 있지만, Pr(I)는 분석적으로 계산 불가능 Optimality - 알고리즘 복잡도 2021. 3. 24. Analysis of the Algorithm 2 Proof (증명법 1. Counterexample - 반례 2. Contraposition - 대우 3. Contradiction - 모순, 귀류: 결론을 부정하고 모순임을 보임 4. Mathematical Induction - 수학적 귀납법 : i가 초기값에 대해 참, i가 k에 대해 참이라고 가정할 때 k+1일 때도 참임을 증명 Analyzing Algorithms and Problems - Correctness 증명하기 1. if the precondition(input data) are satisfied, ex) 정수정렬문제면 인풋이 정수인지 2. then the postcondition(output data) will be true, 3. whe the algorithm terminates A.. 2021. 3. 24. Analysis of the Algorithm 1 Analysis of the Algorithm 실험적 분석: 구현 필수, 실험하지 않은 인풋에 대한 결과를 알 수 없음, 비교할 때 환경이 동일해야 함 이론적 분석: 구현 전 파악, 수행시간을 n함수로 정의, 모든 인풋에 대해 고려, 환경과 상관없는 평가 가능 Worst-Case Analysis - W(n): 최대 basic operation 수를 n으로 표현한 함수. - Analysis Tool 1. Mathematics - Series : the sum of a sequence 2. Logic A => B ㄱA v B ㄱ(A ^ B) ㄱA v ㄱB 드모르간의 법칙 ㄱ(A v B) ㄱA ^ ㄱ 2021. 3. 24. 윈도우 유용한 단축키 모음 win+숫자키 (작업표시줄의 프로그램 활성화) win+shift+숫자키 (같은 프로그램 새 창) win+alt+숫자 (창 속성) win+L (잠그기) win+ctrl+d (가상 데스크탑) win+ctrl+좌우방향키 (가상 데스크탑 이동) win+shift+s (화면 캡쳐 - 부분캡쳐 가능) win+e (탐색기) win+v (클립보드) win+. (이모지) win+m (모두 최소화) win+shift+m (최소화 취소) win+Ctrl+Shift+B (깨우기) 2021. 3. 24. 예외처리 (Exception Handling) 예외처리 (Exception Handling) - 스택 되감기 (Stack unwinding) - 기반 지식 프로그램 메모리(코드 메모리) : 코드를 보유하는 환경. 이 영역에는 다른 객체를 선언할 수 없음. 프로그램이 종료될 때 해제된다. 정적 메모리 : static 키워드를 사용해 정적 변수를 선언하면 정적 메모리에 올라간다. 전역객체와 정적객체를 보유하는 영역. 프로그램이 종료될 때 모든 객체를 정리하고 해제된다. 힙 메모리 : 런타임시점의 객체를 저장할 때 사용. Free 또는 동적 메모리라고도 부른다. new 키워드 사용. 스택 메모리 : 함수의 지역변수, 매개변수 등을 저장. last in first out. c++는 스택에 있는 객체만 이름을 가질 수 있기 때문에 스택 메모리 포인터를 이용해.. 2021. 3. 23. 알고리즘의 과정 - 알고리즘이란 : a detailed step-by-step method for solving a problem (유한 시간 내에) by using a computer. - 과정 1. Problem - 문제 정의: input/ouput 2. Strategy - 전략 세우기 3. Algorithm - 알고리즘 서술: Input / Output / Step(Speecification) 4. Analysis - 알고리즘 분석 - Correctness : 어떤 입력에 대해서도 가능함을 보인다. - Time & Space(Storage) - Optimality : 최적성. problem complexity = algorithm complexity일 때 최적. 5. Implementation - 구현 6. Ver.. 2021. 3. 23. 이전 1 ··· 8 9 10 11 12 13 다음
