# 自定义类型

在电话本算法中,name 和 number 必须一一对应,这在数据变多之后变得很困难,由此引出自定义类型

自定义类型
typedef struct  // 一个容器
{
    string name;
    string number;
}
person;  // 定义了 person 这个数据类型
int main(void)
{
    person people[4];
    people[0].name = "EMMA";
    ...
}

phone book 1
phone book 2

# 线性搜索 linear search

从头到尾依次查找是否是要的值

例子:查 Emma 家的电话

int main(void)
{
    string names[4] = {"EMMA", "RODRIGO", "BRIAN", "DAVID"};
    // 静态初始数组
    for (int i = 0; i < 4; i++)
    //do the folloing 4 times.
    {
        if (strcmp(names[i], "EMMA") == 0)
        // 类型不同,无法直接比较
        //strcmp 需 include<string.h>,用于字符串的比较,相同则返回 0
        {
            printf("Found\n");
            return 0;
        }
    }
    printf("Not found\n");
    return 1;
}

若不加 return 0 ,for 循环会用 if 的条件把数组中每个值都判断一遍,让 if 去打印 found 或者跳过。这里也解决了第一天的问题, return 0 表示运行正确,找到了, return 1 表示没找到。

# 冒泡排序 bubble sort

bubble sort 1

有几个人,相互比较,需要 n-1 次。若恰巧是倒序,每次都进入 IF 语句,则最大运行时间是 (n-1)*(n-1) —> n²,最终决定性的是最高阶项,即 O (n²)。最好的情况,仍需不断检查,为 Ω(n²)。

bubble sort 2

优化之后,最好的情况,仅需依次检查一遍,为 Ω(n)。

# 选择排序 selection sort

selection sort

在每次迭代中,选择一个最小的元素。若恰巧是倒序, n, n-1, n-2, ... , 1 —> n²。最好的情况 12345678 计算机仍然必须看了所有之后,决定 1 还在那里,仍为 n²。

对此我有个问题:swap 这一操作耗时吗?仅仅是查看而并不 swap 呢?

# 二进制搜索 binary search

对于预先排好顺序的一组数,找到中间,与要找的值比较,若大于,去小的那边

binary search

Leap of Faith

recursion
void draw (int h);
int main(void)
{
    int height = get_int("Height: ");
    draw(height);
}
void draw (int h)
{
    if (h == 0)
    {
        return;
    }
    draw(h-1);
    for (int i = 0; i < h; i++)
    {
        printf("#");
    }
    printf("\n");
}

Jast like with any divide-and-conquer approach, I’m calling myself on a smaller probblem.

# 合并排序 merge sort

merge sort

纵向 将 8 个数分成单个数,需要 log2 (8) 次,横向 是 8,所以 O (nlogn)、Ω(nlogn)。

divide

merge 是排序的关键,但是怎样实现?

# 算法的评价

# big O

big O

Big O 指算法可能花费多少时间的上限。用这个表示时,就像是用手挥舞着比划, n n/2 都是线性,2 不再重要,都写作 O(n)log2(n) 中的 2 也不再重要,写作 O(logn)

Size of problem

# omega

omega

Omega 描述最佳情况,即算法可能花费多少时间的下限。

# theta

theta 表示算法具有相同的上限和下限。

theta