Jungle's Blog
📚 文章 🏷️ 标签 🗃️ 分类 👴 关于
Jungle's Blog

目录

Algorithms Analysis

Jungle 出版于 Data Structure
   约 726 字   预计阅读 4 分钟 

Data Structure

Algorithms Analysis

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
  2. Readability
  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 <typename T, std::size_t N>
void printArray(const std::array<T, N> &array) {
    for (auto i = array.begin(); i != array.end(); i++)
        std::cout << *i << " ";
    std::cout << std::endl;
}

template <typename T, std::size_t N>
void BubbleSort(std::array<T, N> &array) {
    /*
     * The reason why we will operate "i--" on the loop
     * When a loop finished the max_element in array[0] 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))$

About Homework

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<int>& 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<int>& vector) {
    int left = 0, right = static_cast<int>(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)$

Data Structure
更新于 2022-11-06