자료구조

• 알고리즘


  문제를 해결하기 위한 체계적 단계
• 알고리즘


  • 입력 (input) : 문제와 관련된 입력이 0 개 이상 존재해야 한다
  • 출력 (output) : 입력을 처리한 출력 (결과)이 반드시 있어야 한다
  • 일반성 (generality) : 같은 유형의 문제에 대해 항상 적용될 수 있어야 한다
  • 유한성 (finiteness) : 입력은 제한된 개수의 명령 단계를 거쳐 출력을 내고 반드시 종료되어야 한다
• 자료형 (Data Type)


  A data type is a collection of objects and a set of operations that act on those objects
• 추상자료형 (Abstract Data Type: ADT)

  An abstract data type (ADT) is a data type that is organized in such a way that the specification of the objects and the operations on the objects is separated from the representation of the objects and the implementation of the operations
• Natural_Number


  • objects: an ordered subrange of the integers starting at zero and ending at the maximum integer (INT_MAX) on the computer
  • functions: for all x, y Nat_Number; TRUE, FALSE Boolean, and where +, -, <, and == are the usual integer operations
• 순서도 (Flow Chart)


  명령의 종류와 기능에 따라 도표를 만들고 명령들의 순서대로 도표를 나열해 표현한 방식
• 의사코드 (Pseudo Code)


  일반적인 언어와 프로그램 코드를 적절히 이용해 명령들을 나열한 방식
• 의사코드 작성방법


  1. 기본 요소

  2. 연산자

  3. 조건문

  4. 다단계 조건문

  5. 반복문
• maxnum


  • algorithm maxnum (a, b, c) {

  x = a;

  if b > x then

  x = b;

  endif

  if c > x then

  x = c;

  endif

  print x;

  }
• 알고리즘 예제 12-3 (1)의 결과는 i=22, x=0
• 알고리즘 예제 12-3 (2)는 정확한 출력을 얻을 수 없는 알고리즘
• 공간복잡도 (Space Complexity)


  프로그램을 실행시켜 완료하는데 필요로 하는 기억 장소의 크기
• 시간복잡도 (Time Complexity)


  프로그램을 실행시켜 완료하는 데 필요한 컴퓨터 시간의 양
• if (조건문) then


  Block start and end is indicated by if (condition) then ... endif
• while (조건문)


  Block start and end is indicated by while (condition) ... endwhile
• (1) The algorithm updates the value of x while i repeats from 0 to 20. The value of x is 10 until i becomes 18, and then x becomes 0 when i is 20. Finally, it increments i by 2 and outputs the result since i no longer meets the loop condition (i<=20). This algorithm receives input i=0, x=1 and terminates with the correct output i=22, x=0.
• (2) Since the value of n is unknown, the algorithm either does not repeat or repeats infinitely. This algorithm cannot execute finite and logical commands, so it cannot obtain accurate output.
• Algorithm Performance Analysis


  Focuses on estimating time and space, regardless of the computer. Complexity Theory determines the time dependent on the computer.
• Space Complexity


  The size of the memory required to complete the program execution.
• Time Complexity


  The amount of computer time required to complete the program execution.
• Fixed space area: The program requires a constant space area regardless of the size of the data being executed.
• Variable space area: The required space area changes according to the number of data. The space area can be 2xn, 3xn, nxn depending on the program.
• Example of space complexity: A program that adds n data requires a space of n+3 (n, tempsum, i).
• In the space complexity calculation, the memory space passed as input parameters is excluded. The memory size required for computation in the function is included.
• Time Complexity


  Analyzes the number of operations performed by the program P, represented as T(P) or f(n) based on the input size n.
• The time complexity analysis method counts the number of statements executed in the program.
• For a program with n=0, the total number of executed statements is 4. For n not 0, the total number of executed statements is 2xn+4.
• The time complexity of the sum function is 2n+3 steps.
• The time complexity of the rsum function is 2n+2 steps.
• The total steps for the sum function is 2n+3, and for the rsum function is 2n+2.
• Program 1.14


  Program 1.11 with count statements added (p.24)
• rsum


  1. count++

  2. if (n)

  3. return rsum(list, n-1) + list[n-1]

  4. count++

  5. return list[0]
• Time Complexity of rsum is 2n+2
• sum


  1. float tempsum = 0

  2. for(i = 0; i < n; i++)

  3. tempsum += list[i]

  4. return tempsum
• Time Complexity of sum is 2n+3
• add


  1. for(i = 0; i < rows, i++)

  2. for(j = 0; j < cols; j++)

  3. c[i][j] = a[i][j] + b[i][j]
• Time Complexity of add is 2rows*cols + 2rows +1
• Big O Notation


  Represents the upper bound of an algorithm's time complexity (worst case)
• Θ (Theta) Notation


  Represents the average time complexity of an algorithm
• Complexity Classes


  • Constant
  • Logarithmic
  • Linear
  • Log-linear
  • Quadratic
  • Cubic
  • Exponential