递归算法的时间复杂度

彻底搞懂递归的时间复杂度_递归排序的时间复杂度-CSDN博客

二分查找(Binary search)：一般发生在一个数列本身有序的时候，要在有序的数列中找到目标数，所以它每次都一分为二，只查一边，这样的话，最后它的时间复杂度是O(logn)

二叉树遍历(Binary tree traversal)：如果是二叉树遍历的话，它的时间复杂度为O(n)。因为通过主定理可以知道，它每次要一分为二，但是每次一分为二之后，每一边它是相同的时间复杂度。最后它的递推公式就变成了图中T(n)=2T(n/2)+O(1)这样。最后根据这个主定理就可以推出它的运行时间为O(n)。当然这里也有一个简化的思考方式，就是二叉树的遍历的话，会每一个节点都访问一次，且仅访问一次，所以它的时间复杂度就是O(n)

二维矩阵(Optimal sorted matrix search)：在一个排好序的二维矩阵中进行二分查找，这个时候也是通过主定理可以得出时间复杂度是O(n)，记住就可以了

归并排序(merge sort)：所有排序最优的办法就是nlogn，归并排序的时间复杂度就是O(nlogn)

gdb调试

目的：复现jyy的调试过程

直接执行make debug会报错，显示no file问题就是boot里的文件是bootblock.o而不是boot.o，所以在其Makefile里添加

1

cp bootblock.o boot.o

复制一份，如何就再次执行make debug 就会出现新的bug

1

gdb.error: "/home/cgz/work/os-workbench/abstract-machine/am/src/x86/qemu/boot/boot.o": not in executable format: file format not recognized

显示格式不能识别，问gpt回答为该种格式不能直接调试，需要启动qemu，连接调试，事实也是这样，

问题不是这个。所以就是Makefile里缺少-ggdb

需要-ggdb提供调试信息，gdb才能调试可执行文件

在

1

abstract-machine/am/src/x86/qemu/boot/Makefile

添加-ggdb可以同时解决打印不出来的问题，不实现stdio里的printf函数也能打印

设置$AM_HOME为pa的框架，改写Makefile不起作用

但是改写为直接clone的

1

/home/cgz/work/os-workbench/abstract-machine/am/src/x86/qemu/boot/Makefile

就能正常使用printf，但是用make debug还是没有标记

1

gdb.error: "/home/cgz/work/os-workbench/abstract-machine/am/src/x86/qemu/boot/boot.o": not in executable format: file format not recognized

造成这个的原因是在文件上没有gdb可以识别的标记

解决方法应该是加上-ggdb应该就可以

但是还是报错没有标记，把bulid生成的.o文件全部删除，再执行也一样。

尝试把py程序代码手动输入，看看能否解决

1
2
3
4

debug:
	qemu-system-i386 -s -S -machine accel=tcg -smp "1,sockets=1" \
		-drive format=raw,file=build/hello-x86-qemu &
	gdb -x debug.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

# Register the quit hook
def on_quit():
    gdb.execute('kill')

gdb.events.exited.connect(on_quit)

# Connect to the remote target
gdb.execute('target remote localhost:1234')

# Load the debug symbols
am_home = os.environ['AM_HOME']
path = f'{am_home}/am/src/x86/qemu/boot/boot.o'
gdb.execute(f'file {path}')

# This is the 0x7c00
gdb.Breakpoint('_start')

# This is where 32-bit code starts
gdb.Breakpoint('start32')

# Continue execution
gdb.execute('continue')

提取出命令

1
2
3
4
5
6
7
8
9
10
11

qemu-system-i386 -s -S -machine accel=tcg -smp "1,sockets=1" -drive format=raw,file=build/hello-x86-qemu &
//打开虚拟机文件夹
gdb am/src/x86/qemu/boot/boot.o

target remote localhost:1234

//然后打断点执行
(gdb)b _start
(gdb)b start 32
(gdb)c

同样的报错

已解决

把Makefile的两行交换位置即可

1
2
3
4
5
6
7
8
9

SRCS := start.S main.c
bootblock.o: $(SRCS) Makefile
        @echo + CC $(SRCS)
        @$(CROSS_COMPILE)gcc -ggdb -static -m32 -fno-pic -Os -nostdlib  -Ttext 0x7c00 -I$(AM_HOME)/am/src -o bootblock.o $(SRCS)
        cp bootblock.o boot.o
        @python3 genboot.py bootblock.o#该pyhton程序的作用是将bootblock.o转换成其他格式供底层程序使用，破坏了其可调试性

clean:
        rm -rf *.o

错误递归

1
2
3
4
5
6
7
8
9

Polynomial& Polynomial::operator=(const Polynomial& p) {
    if (this == &p) return *this;
    delete[] coefficients;
    size = p.size;
    coefficients = new double[size];
    for (int i = 0; i < size; i++)
        coefficients[i] = p.coefficients[i];
    return *this;
}

1
2
3
4
5
6

Polynomial& Polynomial::operator=(const Polynomial& p) {
    if (this == &p) return *this;
    delete[] coefficients;
    *this = Polynomial(p);//重复调用了=
    return *this;
}

面向对象

封装，继承和多态

多态

1. 覆盖（也叫重写）（override）： 是指子类重新定义父类的虚函数的做法，是在类中才有的概念
2. 重载（overload）： 是指允许存在多个同名函数，而这些函数的参数表不同（或许参数个数不同，或许参数 类型不同，或许两者都不同）不一定是在类中的

重写与重载的本质区别是,加入了override的修饰符的方法,此方法始终只有⼀个被你使用的方法

return by reference