# Data Structure

## Algorithm

Define: A finite, clearly specified sequence of instructions to be followed to solve a problem.(not a program)

### Five features

1. Finiteness
2. Definiteness
3. Effectiveness
4. Input
5. Output

### Design Requirements

1. Correctness
3. Robustness
4. High efficiency and low memory capacity

## Algorithm Analysis

Computing time and memory space are two important resources.

### Running time Analysis

The estimation of the running time of algorithms.

The running times of algorithms can be changed because of the platform, the properties of the computer, etc.

### Time complexity

We use asymptotic notations($O,\Omega,\theta$)

1. compare relative growth
2. compare only algorithms

$f(n) \rightarrow Frequency\ Count$

$Then\ T(n) = O(f(n))$

$if\ T(n) = O(f(n)),then\ T(n) \leq C*f(n), C \in R$

Constants can be ignored!!!

Lower order terms are ignored!!!

Example

 1 2 3 4 5 6  public static void sum(int[] array, int n) { int s = 0; for (int i = 0; i < n; i++) s += array[i]; System.out.format("%d", s); } 

$f(n) = 1 + n + n + 1 = 2n + 2$

$T(n) = O(f(n)) = O(2n + 2) = O(n) \rightarrow Linear\ order$

Time complexity is related with input Example:

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27  //The function is to print all the element in array; template void printArray(const std::array &array) { for (auto i = array.begin(); i != array.end(); i++) std::cout << *i << " "; std::cout << std::endl; } template void BubbleSort(std::array &array) { /* * The reason why we will operate "i--" on the loop * When a loop finished the max_element in array to array[i - 1] will be in the end of the array by swap * so when we scan the array next time we needn't care the element after array[i - 1] * so we will operate "i--" to greater the Algorithm effective */ for (std::size_t i = N - 1, count = 1; i > 0; i--, count++) { bool flag = true; for (std::size_t j = 0; j < i; j++) if (array[j] > array[j + 1]) { std::swap(array[j], array[j + 1]); flag = false; } if (flag) break; } printArray(array); } 

$T(n)\ can\ be\ O(n), but\ also\ can\ O(n^2)$

#### Relations

$O(1) < O(\log n) < O(n) < O(n\log n) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)$

$if\ T1(n) = O(f(n))\ and\ T2(n) = O(g(n))\ then$

a) $T1(n) + T2(n) = max (O(f(n)), O(g(n)))$

b) $T1(n) * T2(n) = O(f(n)* g(n))$

analysis of the running time

 1 2 3 4 5 6  int sum = 0; for (int i = 1; i < n; i++) for (int j = 1; j < i * i; j++) if (j % i == 0) for (int k = 0; k < j; k++) sum++; 

analysis code block

 1 2 3 4  for (int j = 1; j < i * i; j++) if (j % i == 0) //->step = 1 for (int k = 0; k < j; k++) //->step j when j = ki sum++; 

$so\ the\ step = 1 + 1 + 1 + i + 1 + 1 + … + 2i + 1 + 1 + … + i * i$ $= i^2 + i(1 + 2 + 3 + … + i) = i^2 + i^3 = O(i^3)$

so the code became

 1 2  for (int i = 1; i < n; i++) O(i^3) 

$so\ T(n) = O(n^4)$

Give an efficient algorithm to determine if there exists an >integer i such that $a_i = i$ in an array of integers $a_1< a_2 < a_3< . . . < a_n$. What is the running time of your algorithm?

Traverse:

 1 2 3 4 5 6  bool traverse(const std::vector& vector) { std::size_t length = vector.size(); for (std::size_t i = 0; i < length; i++) if (vector[i] == i) return true; return false; } 

$T(n) = O(n)$

Binary Search

 1 2 3 4 5 6 7 8  bool BinSearch(const std::vector& vector) { int left = 0, right = static_cast(vector.size()); while (right - left > 1) { int middle = (left + right) >> 1; vector[middle] < middle ? left = middle : right = middle; } return vector[right] == right; } 

$T(n) = O(\log n)$