Sakura
或许是不知梦的缘故，流离之人追逐幻想
FRIENDS
WongAzinSakura

算法导论(一)

2020-02-27

数据结构课程笔记

时间复杂度T(n)

定义：输入规模为n时的最长运行时间。

三种复杂度：

  1. 最坏复杂度，T(n)的上界，输入情况中的最坏情况。
  2. 平均复杂度，每种输入的运行时间，乘以那种输入出现的概率。
  3. 最好复杂度，假象，T(n)的下界，输入情况中最好情况。

复杂度的渐进表示

θ:一个公式，弃去它的低阶项，并忽略前边的常数因子。

当n趋于无穷大时θ(n^2)迟早大于θ(n^3)。一个for循环的时间复杂度等于循环次数乘以循环体代码的复杂度。if-else复杂度取决于条件判断复杂度和两个分支复杂度。取三者中最大的

复杂度比较

2^n>n^2>nlogn>n>logn>1。常用降低复杂度是将n^2装换为nlogn。

例：输入一组序列a1，a1直到an。按从小到大顺序排序输出。

法1.插入排序

伪代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
INSERTION-SORT(A)

for j=2 to length[A]

do key=A[j]

Insert A[j] into the sorted sequence A[1..j-1].

i=j-1

while i>0 andA [i] >key

do A[i+1] =A[i]

i=i-1

A[i+1] =key

c：

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
28
#include <stdio.h>

void insertion_sort(int array[], int first, int last) {
    int i, j;
    int temp;
    for (i = first + 1; i <= last; i++) {
        temp = array[i];
        j = i - 1;
        while ((j >= 0) && (array[j] > temp)) {   
           array[j + 1] = array[j];								//与已排序的数逐一比较，大于temp时，该数移后
            j--;
        }
        if (j != i - 1)                                   //存在大于temp的数时
            array[j + 1] = temp;
    }
}

int main() {
    int a[8], i;
    for (i = 0; i < 8; i++) {                             //输入要排序的数，保存到数组里
        scanf("%d", &a[i]);
    }
    int j;
    insertion_sort(a, 0, 7);                   			  //调用insertion_sort方法
    for (j = 0; j < 8; j++)                               //将排好序的数组输出出来
        printf("%d ", a[j]);
    return 0;
}

法2: 归并排序

c：

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <stdio.h>
 
void Merge(int sourceArr[],int tempArr[], int startIndex, int midIndex, int endIndex)
{
    int i = startIndex, j=midIndex+1, k = startIndex;
    while(i!=midIndex+1 && j!=endIndex+1)
    {
        if(sourceArr[i] > sourceArr[j])
            tempArr[k++] = sourceArr[j++];
        else
            tempArr[k++] = sourceArr[i++];
    }
    while(i != midIndex+1)
        tempArr[k++] = sourceArr[i++];
    while(j != endIndex+1)
        tempArr[k++] = sourceArr[j++];
    for(i=startIndex; i<=endIndex; i++)
        sourceArr[i] = tempArr[i];
}
 
//内部使用递归
void MergeSort(int sourceArr[], int tempArr[], int startIndex, int endIndex)
{
    int midIndex;
    if(startIndex < endIndex)
    {
        midIndex = startIndex + (endIndex-startIndex) / 2;//避免溢出int
        MergeSort(sourceArr, tempArr, startIndex, midIndex);
        MergeSort(sourceArr, tempArr, midIndex+1, endIndex);
        Merge(sourceArr, tempArr, startIndex, midIndex, endIndex);
    }
}
 
int main()
{
    int a[8] = {10,4,6,3,8,2,5,7};
    int i, b[8];
    MergeSort(a, b, 0, 7);
    for(i=0; i<8; i++)
        printf("%d ", a[i]);
    printf("\n");
    return 0;
}
归并排序

不断二分，分到不能分割，然后比大小，10 4变成4 10,6 3变成3 6，然后3和4比，4和6比，6和10比，排成3 4 6 10，然后是比后半部分，同理，得到2 5 7 8，然后2和3比，小的存进去，3和5比等等等等。

b链插入a（）

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include <stdio.h>
#include <stdlib.h>
//第二个链表整体插入第一个，应该也算合并吧

typedef struct LNode *List;
struct LNode {                                      //声明结构体,
    int Data;
    List Next;
};
typedef LNode *L;

List initLink(int arr[]);                                    //声明各个函数

void TravelList(List final);

List Find(int n, List PtrL);

List MergeList(List s, int i, List PtrL);

int main() {
    int arr[4] = {6, 7, 8, 4};
    int arr2[4] = {4, 6, 9, 1};
    printf("第一行数");
    List p = initLink(arr);                            //初始化链表,得到链表1头
    TravelList(p->Next);                                //调函数递归输出链表1数据
    printf("\n");
    printf("第二行数");
    List q = initLink(arr2);                           //初始化链表2
    TravelList(q->Next);
    printf("\n");
    List final = MergeList(q->Next, 3, p->Next);    //将表1表2传给合并方法，中间数字为表二插在表一的哪个位置后边,
    printf("合并后:");
    TravelList(final);
}

void TravelList(List final) {
    if (final == NULL)
        return;                                         //递归终止
    else {
        printf("%d ", final->Data);                     // 输出当前结点的数据域
        TravelList(final->Next);                        // p指向后边节点继续递归
    }
}

List initLink(int arr[]) {
    List p = (List) malloc(sizeof(List));               //创建一个头结点,动态分配一下空间
    List temp = p;                                      //声明一个指针指向头结点，用于遍历链表
        //生成链表
    for (int i = 0; i < 4; i++) {
        //创建节点并初始化
        List a = (List) malloc(sizeof(L));
        a->Data = arr[i];
        a->Next = NULL;
        //建立新节点与直接前驱节点的逻辑关系
        temp->Next = a;
        temp = temp->Next;
    }
    return p;
}

int getlength(List PtrL) {                              //得到链表长度,防止插入位置超过长度,有点可有可无
    List s = PtrL;
    int j = 0;
    while (s) {
        s = s->Next;
        j++;
    }
    return j;
};

List Find(int n, List PtrL) {                            //查找要插入的位置，返回要插入位置的头节点
    List p = PtrL;
    int i = 0;
    while (p != NULL && i < n) {
        p = p->Next;
        i++;
    }
    if (i == n)
        return p;
    else return NULL;
};

List MergeList(List s, int i, List PtrL) {              //合并函数,其实就是插入.插到a位置,表二尾指向原来表一的第a个节点,a-1指向表二头.
    List p, k;
    int length = getlength(s);
    p = Find(i - 1, PtrL);
    if (i > 0 && p != NULL) {
        k = s;
        for (i = 0; i < length - 1; i++) {
            k = k->Next;
        }
        k->Next = p->Next;
        p->Next = s;
        return PtrL;
    }
}

Author: Sakura

Link: http://sakur-a.cn/2020/02/27/%E7%AE%97%E6%B3%95%E5%AF%BC%E8%AE%BA(%E4%B8%80)/

Copyright: All articles in this blog are licensed under CC BY-NC-SA 3.0 unless stating additionally.

< PreviousPost
day01_jQueryNextPost >
Clion安装教程
CATALOG
  1. 1. 时间复杂度T(n)
    1. 1.0.1. 三种复杂度：
    2. 1.0.2. 复杂度的渐进表示
    3. 1.0.3. 复杂度比较