[DS]Unit 1. Introduction(1)

• Inductive Proof(귀납법) :  어떤 명제의 기본케이스가 참일때, f(n)이 참이라고 가정하고 f(n+1) 역시 참이면 이 명제는 항상 참이 된다.
  EX) All horses are the same color
  - Base case : One horse(n이 1이라고 가정할 때, 해당 그룹의 모든 말은 같은 색이다.)
  - Inductive step : Assume that n horses are always the same color. what about n+1 horese?
                         n+1의 상황에서 말 한마리를 제외한 n마리의 말은 모두 같은 색이다. 제외한 말을 다시 그룹에
                         넣고 다른 말을 제외해도 n마리의 말들은 같은 색이다. 그러므로 n+1의 말은 모두 같은 색이다.
  - if n is 2?(반례) : n이 2라면 a가 검정색, b가 하양색으로 색이 달라도 n+1에서 한마리를 제거했을 때 남은 n그룹                           (이 경우엔 한마리)의 말은 같은 색(검정색이거나 하양색)이다. 이러한 경우 n 그룹의 말의 색은
                         같지만, n+1마리 그룹의 말은 색이 다르다.
• Introduction
  - Data Structure? 자료구조는 컴퓨터가 data를 구조화(organize)하는 효율적인 방법을 의미한다. 
  - Classification by data form
  

  Simple Structure	Primitive data types (integer, real number, character, string)
  Linear Structure	1-to-1 relationship between front and rear components (array, list, linked list, stack, queue, deque, ....)
  Non-Linear Structure	1-to-N or M-to-N relationship between front and rear components (tree, graph, ....)
  File Structure	set of records (sequential file, indexed file, direct file,....)

• Data structure VS algorithm
  - Data Structure: Efficient way of organizing data for computer
  - Algorithm: Efficient way of solving a problem
  => for Performance!
  Efficiency means performance of time(how fast) and space(how small).
  
  
• Measuring program efficiency
  - Runtime of a program often grows with the input size.
  - Calculating average runtime isn't easy.
  => worst-case runtime
  - Measuring runtime
  

  long startTime = System.currentTimeMillis();
  /*(run the algorithm)*/
  long endTime = System.currentTimeMillis();
  long elapsed = endTime - startTime;​

  - Dependency
  (1) Time consuming
  (2) Hardware dependency
  (3) Language dependency
  (4) Compiler dependency
  (5) OS dependency
  (6) Many other dependency
  ...
  
  
• Seven important functions
  - constant ≈1
  - logarithmic ≈ log n
  - linear ≈ n
  - N log n ≈ n log n
  - Quadratic ≈ n² 
  - Cubic ≈ n³
  - Exponential ≈ 2ⁿ

---

참고문헌 : DATA STRUCTURES & ALGORITHMS(6th Edition)
https://en.wikipedia.org/wiki/All_horses_are_the_same_color