丙午🐎年

acc8226 的博客

发表于 更新于 分类于

今天我们讲一种针对有序数据集合的查找算法：二分查找（Binary Search）算法，也叫折半查找算法。

老规矩，我们还是来看一道思考题。假设我们有 1000 万个整数数据，每个数据占 8 个字节，如何设计数据结构和算法，快速判断某个整数是否出现在这 1000 万数据中？ 我们希望这个功能不要占用太多的内存空间，最多不要超过 100MB，你会怎么做呢？带着这个问题，让我们进入今天的内容吧！带着这个问题，让我们进入今天的内容吧！

无处不在的二分思想

二分查找针对的是一个有序的数据集合，查找思想有点类似分治思想。每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为 0。

O(logn) 惊人的查找速度

二分查找是一种非常高效的查找算法，高效到什么程度呢？我们来分析一下它的时间复杂度。我们假设数据大小是 n，每次查找后数据都会缩小为原来的一半，也就是会除以 2。最坏情况下，直到查找区间被缩小为空，才停止。

阅读全文 »

发表于 更新于 分类于

递归树与时间复杂度分析

我们前面讲过，递归的思想就是，将大问题分解为小问题来求解，然后再将小问题分解为小小问题。这样一层一层地分解，直到问题的数据规模被分解得足够小，不用继续递归分解为止。

如果我们把这个一层一层的分解过程画成图，它其实就是一棵树。我们给这棵树起一个名字，叫作递归树。我这里画了一棵斐波那契数列的递归树，你可以看看。节点里的数字表示数据的规模，一个节点的求解可以分解为左右子节点两个问题的求解。

通过这个例子，你对递归树的样子应该有个感性的认识了，看起来并不复杂。现在，我们就来看，如何用递归树来求解时间复杂度。

归并排序的原理我就不详细介绍了，如果你忘记了，可以回看一下第 12 节的内容。归并排序每次会将数据规模一分为二。我们把归并排序画成递归树，就是下面这个样子：

阅读全文 »

发表于 更新于 分类于

1 安装 gcc 环境

选择 1 Mingw-w64

Downloads - MinGW-w64

选择 2 MSYS2

msys2 包地址 ｜ 镜像

以自解压版为例
https://mirrors.tuna.tsinghua.edu.cn/msys2/distrib/x86_64/msys2-base-x86_64-20230718.sfx.exe

1. 下载自解压程序
https://mirrors.tuna.tsinghua.edu.cn/msys2/distrib/x86_64/msys2-base-x86_64-20230718.sfx.exe

2. 双击 ucrt64.exe 进入终端并执行

1
pacman -S --needed base-devel mingw-w64-x86_64-toolchain

2 从 Hello World 开始

编辑

创建 hello.c，输入以下代码：

1
2
3
4
5
6
#include <stdio.h>

int main() {
    printf("Hello world!\n");
    return 0;
}

编译

编译器可以将源代码转换成机器语言，在编译过程中，会找出错误并报告。这个阶段的输入是在编辑期间产生的文件，常称为源文件。

gcc -c hello.c

注：GCC 是由 GNU 开发的编程语言编译器，用来编译 C 语言程序。

链接

链接器将源代码文件中由编译器产生的各种对象模块组合起来，再从 C 语言提供的程序库中添加必要的代码模块，将它们组合成一个可执行文件。

gcc -o hello hello.o

多数情况下，我们可以通过 gcc -o hello hello.c 命令，调用编译器 GCC 对文件 abc.c 进行编译，完成了 “预处理-编译-汇编-链接”，生成了可执行文件 hello。

运行

./hello

3 IDE 选择

Visual Studio 是非常全能的选择，界面也较为现代。

发表于 更新于 分类于

什么是计算机程序

程序：一组计算机能识别和执行的指令。每一条指令是计算机执行特定的操作；计算机的一切操作都是由程序控制的，离开程序，计算机将一事无成。

什么是计算机语言

[发展阶段]

  1. 机器语言 一种计算机能直接识别和接受的二进制代码称为机器指令。机器指令的集合就是计算机的机器语言。
  2. 符号语言 为了克服机器语言的上述缺点，用一些英文字母和数字表示一个指令，显然计算机并不能直接识别和执行符号语言的指令。一般，一条符号语言的指令对应一条机器指令。该过程称为"代真"或"汇编"，因此，符号语言又称为符号汇编语言或汇编语言。
  3. 高级语言 克服了低级语言的缺点。
    阅读全文 »

发表于 更新于 分类于

c 语言的八进制以 0 开头

& 和 && 左边是非短路与, 右边是短路与.

while(!e) 表示 !e != 0 则 与 e == 0 等价

什么时候使用 while, for while, for 循环

如果有固定的循环次数用 for
如果必须执行一次, 用 do while
否则用 while

在 include <stdbool.h> 后可以使用 bool, true 和 false 了

0%