Tracy's Studio.

算法题部分复习

算法
字数统计: 1.1k阅读时长: 4 min
2022/03/29 Share

算法刷题部分复习

参考资料：

代码随想录： https://programmercarl.com/

算法复杂度分析

时间复杂度

时间复杂度$O(1)<O(\log n)<O(n)<O(n \log n)<O(n^2)$.

对于算法的时间复杂度要学会分析，从而推断程序运行的时间。

空间复杂度

单个变量的空间复杂度是$O(1)$，一维数组的空间复杂度是$O(n)$，二维数组的空间复杂度即为$O(n^2)$。

递归算法的时间复杂度

算法复杂度=递归次数*递归操作次数

例1 求x的n次方：

给定$x$和$n$，求$f(x)=x^n$

解法1：

思路：当n=0的时候返回1，否则进入循环，用$res$记录结果，每次都乘上$x$。

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <iostream>
using namespace std;

int f(int x, int n){
    int res = 1;
    if(n==0)	return res;
    else{
        while(n--){
            res*=x;
        }
    }
    return res;
}

此时的算法复杂度为$O(n)$。

解法2：

思路：用递归法，每次都求$f(x, n/2)$，避免重复的计算。

1
2
3
4
5
6
7
8
9
#include <iostream>
using namespace std;

int f2(int x, int n){
    if(n==0)	return 1;
    int t = f2(x, n/2);
    if (n%2==0)	return t*t;
    return t*t*x;
}

此时算法的复杂度是$O(\log n)$.

例2 求Fibonacci数列

问题：求Fibonacci数列，$f(0) = 0,f(1) = 1,f(n)=f(n-1)+f(n-2)$. 若$n<0$，则$f(n)=0$.

解法1：

思路：递归法，每次都递归地求$f(n-1)$和$f(n-2)$.

1
2
3
4
5
6
7
8
#include <iostream>
using namespace std;

int Fibonacci1(int n){
	if(n<=0)	return 0;
    if(n==1)	return 1;
    return Fibonacci1(n-2) + Fibonacci1(n-1);
}

此时算法的时间复杂度为$O(2^n)$，空间复杂度为$O(n)$。

解法2：

思路：非递归法，每次分别用三个数字记录$f(n-2)$、$f(n-1)$和$f(n)$.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
using namespace std;

int Fibonacci2(int n){
    if(n<=0)	return 0;
    if(n==1)	return 1;
    // f(1) -- f(n-2)
    int a = 1;
    // f(2) -- f(n-1)
    int b = 1;
    while(n>2){
        // f(n) = f(n-1) + f(n-2)
        c = a+b;
        // b <- f(n)
        b = c;
        // a <- f(n-1)
        a = b;
    }
    return c;
}

解法3：

递归法，但是每次都用数值代替递归的过程。

1
2
3
4
5
6
7
8
9
#include <iostream>
using namespace std;

int Fibonacci(int first, int second, int n){
    if(n<=0)	return 0;
    if(n<3)		return 1;
    if(n==3)	return first+second;
    return Fibonacci(second, first+second, n-1);
}

此时，算法的复杂度为$O(n)$.

内存管理

C++中的内存管理

C++中存在内存泄漏，主要是用户在new了对象后没有进行释放。

C++程序运行时，内存主要分为两个部分：固定部分和可变部分。

  • 固定部分
    • 代码
      • 代码的二进制代码
    • 数据
      • 静态参数、常量和全局变量等
  • 可变部分
    • 堆区
      • 动态开辟的空间，存放new出来的对象在堆区中的真实数据，需要用户回收。
    • 栈区
      • 代码运行过程中的变量、递归栈所需的空间、形参、局部变量等。
Python中的内存管理

python中的万物皆对象，封装好了给用户。内存管理是由私有堆空间管理的，所有的python对象和数据结构都存储在私有堆空间中。程序员没有访问堆的权限，只有解释器才能操作。

Java中的内存管理

Java使用JVM进行内存管理。不了解jvm内存管理的机制，很可能会因一些错误的代码写法而导致内存泄漏或内存溢出。

内存对齐

内存对齐主要针对两个方面的问题：

① 平台。不是所有的硬件平台都能访问任意内存地址上的任意数据，某些硬件平台只能在某些地址处取某些特定类型的数据，否则抛出硬件异常。为了同一个程序可以在多平台运行，需要内存对齐。

② 硬件。经过内存对齐后，CPU访问内存的速度大大提升。

1
2
3
4
struct node{
    int num;
    char c;
}st;

该结构体的大小为8个字节（对齐后）。若不进行内存对齐，则会存在需要二次寻址、一次合并的需求。

原文作者：Tracy

原文链接：http://tracywoo.cn/2022/03/29/算法题部分复习/

发表日期：March 29th 2022, 9:15:35 am

更新日期：March 29th 2022, 9:24:24 am

版权声明：本文采用知识共享署名-非商业性使用4.0国际许可协议进行许可

CATALOG
  1. 1. 算法刷题部分复习
    1. 1.1. 算法复杂度分析
      1. 1.1.0.1. 时间复杂度
      2. 1.1.0.2. 空间复杂度
      3. 1.1.0.3. 递归算法的时间复杂度
        1. 1.1.0.3.1. 例1 求x的n次方：
        2. 1.1.0.3.2. 例2 求Fibonacci数列
      4. 1.1.0.4. 内存管理
        1. 1.1.0.4.1. C++中的内存管理
        2. 1.1.0.4.2. Python中的内存管理
        3. 1.1.0.4.3. Java中的内存管理
      5. 1.1.0.5. 内存对齐
Total : 20
2022
2021
2020
2019
CRL others hexo MOEA ML git node markdown 算法 写论文小技巧 PGM pgm
博客 ML MOEA