Fabian备忘录

人类资格证考核中

发表于 更新于 分类于 ，
本文字数： 5.2k

什么是大O

n表示数据规模，则表示运行算法所需要执行的指令数，和成正比。

一个算法有多个步骤，每个步骤规模相同但时间复杂度不同，最终的时间复杂度以最高的那个为准。

 

对数据规模的概念

如果想要在1s之内解决问题：

  • 的算法可以处理大约级别的数据；
  • 的算法可以处理大约级别的数据；
  • 的算法可以处理大约级别的数据；

这个结论只是执行简单的数据操作，实际还需要再低估一下。

 

空间复杂度

  • 多开一个辅助数组：;
  • 多开一个辅助的二维数组：
  • 多开常数空间：;

需要注意：递归调用是有空间代价的，递归的深度就是空间复杂度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//计算n以内数据的和

//空间复杂度O(1)
int sum1(int n)
{
    assert(n >= 0);
    int ret = 0;
    for(int i=0;i<=n;i++)
    {
        ret += i;
    }
    return ret;
}

//递归调用：空间复杂度O(n)
int sum2(int n)
{
    assert(n>=0);
    if(n == 0)
        return 0;

    return n + sum2(n-1);
}

 

简单的时间复杂度分析

O(1)

常数级的算法很简单，没有数据规模的变化

1
2
3
4
5
6
7
// O(1)
void swapTwoInts(int &a , int &b){
    int temp = a;
    a = b;
    b = temp;
    return;
}

O(n)

O(n)的算法典型的特征就是有个循环，并且循环的次数和n相关。

其实正常来说，应该是，其中C是个常数，且不一定大于1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// O(n)
int sum(int n){

    assert(n >= 0);

    int ret = 0;
    for( int i = 0 ; i <= n ; i ++ )
        ret += i;
    return ret;
}

//字符串反转，只需要进行1/2次的swap操作即可
void reverse(string &s){

    int n = s.size();
    for(int i = 0 ; i < n/2 ; i ++)
        swap( s[i] , s[n-1-i] );
    return;
}

O(n^2)

见到算法内部有双重循环，每层循环都是n相关基本就八九不离十了。

1
2
3
4
5
6
7
8
9
10
11
12
//选择排序算法
void selectionSort(int arr[], int n){

    for(int i = 0 ; i < n ; i ++){
        int minIndex = i;
        for( int j = i + 1 ; j < n ; j ++ )
            if( arr[j] < arr[minIndex] )
                minIndex = j;

        swap( arr[i] , arr[minIndex] );
    }
}

千万要注意两层循环都要和n相关，不要看到双重循环就认为是

1
2
3
4
5
6
7
8
9
10

//第二重循环哪怕循环300w次，这个也是O(n)
void printInformation(int n){

    for( int i = 1 ; i <= n ; i ++ )
        for( int j = 1 ; j <= 30 ; j ++ )
            cout << "Class " << i << " - " << "No. " << j << endl;
    return;
}

O(logn)

经典的二分查找法：

1
2
3
4
5
6
7
8
9
10
11
12
//二分查找法
int binarySearch(int arr[], int n, int target){

    int l = 0, r = n-1;
    while( l <= r ){
        int mid = l + (r-l)/2;
        if(arr[mid] == target) return mid;
        if(arr[mid] > target) r = mid - 1;
        else l = mid + 1;
    }
    return -1;
}

 

将数字整形转化为字符串：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
string intToString(int num){

    string s = "";
    string sign = "+";
    if(num < 0){
        num = -num;
        sign = "-";
    }

    while(num){
        s += '0' + num % 10;
        num /= 10;
    }

    if(s == "")
        s = "0";

    reverse(s);
    if(sign == "-")
        return sign + s;
    else
        return s;
}

分析算法思想，核心在" num /= 10"步中，就是n经过几次“除以10”操作后等于0，那么就是;

 

虽然上面两个例子，一个是以2为底，一个是以10为底，但都是，这个可以通过对数函数的换底公式来理解：有换底公式，可见和之间只相差一个常数，在时间复杂度下可以直接理解为

 

还需要注意，双重循环也可能出现logN的复杂度，需要注意量增长的规模：

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
//复杂度:O(nlogn)
void hello(int n){

    for( int sz = 1 ; sz < n ; sz += sz )
        for( int i = 1 ; i < n ; i ++ )
            cout << "Hello, Algorithm!" << endl;
}

//外层循环每次增长可以理解为sz*2
//其实就可以理解为n经过几次“除以2”的操作后等于1，外层循环复杂度O(logn)
//内层循环复杂度是O(n)
//合起来是O(nlogn)



//判断是否为素数
// O(sqrt(n))
bool isPrime(int num){

    if( num <= 1 ) return false;
    if( num == 2 ) return true;
    if( num % 2 == 0 ) return false;

    for(int x = 3 ; x * x <= num ; x += 2)
        if( num%x == 0 )
            return false;

    return true;
}

//

 

递归算法的复杂度分析

面对递归算法需要具体问题具体分析。

递归中只会进行一次递归调用

如果递归函数中只进行一次递归调用，递归深度为depth，在每个递归函数中的时间复杂度为T，则总体的时间复杂度为，既只需关注递归的深度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//递归调用的二分查找法
int binarySearch(int arr[], int l, int r, int target){

    if(l > r)
        return -1;

    int mid = l + (r - l) / 2;
    if(arr[mid] == target)
        return mid;
    else if(arr[mid] > target)
        return binarySearch(arr, l, mid - 1, target);
    else
        return binarySearch(arr, mid + 1, r, target);

}

  二分查找法很容易用递归实现，上述代码每次调用时，内部要么直接返回，要么数组左半边调用递归，要么数组右半边调用递归，只会调用一次，所以分析时间复杂度只有看递归的深度即可。

  每次调用数组减少一半，是典型的logn情况，所以复杂度为

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// sum,O(n)
int sum(int n){

    assert(n >= 0);

    if(n == 0)
        return 0;
    return n + sum(n - 1);
}

// 求x的n次方：O(logn)
double pow(double x, int n){

    assert(n >= 0);

    if(n == 0)
        return 1.0;

    double t = pow(x, n / 2); //每次减半，logn
    if(n % 2)
        return x * t * t;

    return t * t;
}

递归中进行多次递归调用

当递归中有多次递归调用时，就需要关注递归调用的次数了。如果递归中只调用一次，深度就是次数，但如果调用了多次，那么深度和次数就是两个概念了。

1
2
3
4
5
6
7
8
9
10
11
//O(2^n)
//这个是指数级的算法，是个非常慢的算法
int f(int n)
{
    assert(n >= 0);

    if(n == 0)
        return 1;

    return f(n-1) + f(n-1);
}

 

均摊复杂度分析

  有时候会遇到这种情况：解决某个问题时运用了一系列算法，某个算法的复杂度很高，但这个算法可以降低其他算法的复杂度，这时候就需要计算分摊复杂度。

  均摊复杂度的经典问题就是动态数组vector。

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
template <typename T>
class MyVector{

private:
    T* data;
    int size;       // 存储数组中的元素个数
    int capacity;   // 存储数组中可以容纳的最大的元素个数

    // 复杂度为 O(n)
    void resize(int newCapacity){

        assert(newCapacity >= size);
        T *newData = new T[newCapacity];
        for( int i = 0 ; i < size ; i ++ )
            newData[i] = data[i];
        delete[] data;

        data = newData;
        capacity = newCapacity;
    }

public:
    MyVector(){

        data = new T[100];
        size = 0;
        capacity = 100;
    }

    ~MyVector(){

        delete[] data;
    }

    // 平均复杂度为 O(1)
    void push_back(T e){
        //当元素到达容量上限时，需要调用resize扩大空间
        if(size == capacity)
            resize(2 * capacity);

        data[size++] = e;
    }

    // 平均复杂度为 O(1)
    T pop_back(){

        assert(size > 0);
        size --;

        return data[size];
    }

};

 

 

  上面的代码只在push操作时resize了空间，但是没有在pop操作时resize空间。我们当然可以参考push操作，在pop到capacity一半时resize容量，但这里涉及一个问题，就是要防止复杂度震荡。

  考虑这个问题：当push到临界点时resize一倍空间，然后立即pop，此时又resize为一半，然后立即push，这种极端场景下时间复杂度无法均摊，会退化为。

  如果想避免这种场景，可以不再临界点处resize，当pop操作到达capacity的1/4处时，resize为1/2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 平均复杂度为 O(1)
T pop_back(){

    assert(size > 0);
    T ret = data[size-1]; //这里一定要提前拿出来，resize操作会修改data
    size --;

    // 在size达到静态数组最大容量的1/4时才进行resize
    // resize的容量是当前最大容量的1/2
    // 防止复杂度的震荡
    if(size == capacity / 4)
        resize(capacity / 2);

    return ret;
}

发表于 更新于 分类于
本文字数： 2.2k

机器数和真值

机器数：一个数在计算机中的二进制表示形式，叫做这个数的机器数。

机器数是带符号的，在计算机中用一个数的最高位存放符号，正数为0，负数为1；

比如：十进制数+3，就是00000000000000000000000000000011；十进制数-3，就是10000000000000000000000000000011；（int值占4字节）；这个例子只是整型数，浮点数有其他表达方式。

 

真值：真正的数学意义上的数值。因为机器数第一位是符号位，所以机器数的形式就不等于真正的数值。

 

补码

按照上面的机器数的表示方法有一个问题，第一位用作符号位的话，这个数的表示范围会变小。所以计算机中存储用的并不是机器数，而是补码。

 

无符号数的编码

用一个函数（Binary to Unsigned的缩写，长度为w）来表示：

eg:

 

有符号数的补码

用一个函数（Binary to Two`s-complement的缩写，长度为w）来表示：

eg:

 

补码数值范围

数 8位字长 16位字长 32位字长 64位字长
UMax 0xFF
255		 0xFFFF
65535		 0xFFFFFFFF
4294967295		 0xFFFFFFFFFFFFFFFF
18446744073709551615
TMin 0x80
-128		 0x8000
-32768		 0x80000000
-2147483648		 0x8000000000000000
-9223372036854775808
TMax 0x7F
127		 0x7FFF
32767		 0x7FFFFFFF
2147483647		 0x7FFFFFFFFFFFFFFF
9223372036854775807
-1
0		 0xFF
0x00		 0xFFFF
0x0000		 0xFFFFFFFF
0X00000000		 0xFFFFFFFFFFFFFFFF
0X0000000000000000

需要注意，无符号数中0xFFFFFFFF是最大值，但有符号数中这个值代表-1；还要注意有符号数中的最小值是0x80000000;

 

字节序（Byte Ordering）

以32位机器为例，一个字有32bits字长，占用4bytes，在内存中有以下两个存放方式：

  1. 大端法（Big Endian）:大多数IBM机器、Internet传输；

  1. 小端法（Little Endian）:Inter兼容机

个人机器基本上都是小端表示法。

补码的意义

  我们在设计软件系统时总是希望软件系统尽可能的简单通用。于是人们希望在只有加法运算器的情况下设计一种方法能实现减法运算。

  以时间为例：表盘一圈12个小时，现在是8点，那么3小时前是5点，9小时以后还是5点(8+9-12)，这里进行的是模12的操作。所以8-3和8+9的结果是一样的；我们就可以用9来表示-3，如果想计算8-3，那么就用加法器计算8+9；

  当然单纯的这么想是有问题的，以时间为例我们可以得到一个对照表，遇见12就清零：

0 -1 -2 -3 -4 -5 -6 -7 -8 -9 -10 -11
0 11 10 9 8 7 6 5 4 3 2 1
  • 5-3 ==> (5+9)%12=2
  • 3-5 ==> (3+7)%12 = 10 ==>-2

  我们计算3-5的时候，得到的值是10，我们可以在对照表中得到10对应的值是-2，但我们计算5-3的时候，得到的值是2，我们却不需要找对应的值。计算机如何区分什么时候要找对应的值，什么时候不需要呢？

  可以对表进行一些修改：

0 -1 -2 -3 -4 -5 -6 5 4 3 2 1
0 11 10 9 8 7 6 5 4 3 2 1
  • 5-3 ==> (5+9)%12=2 ==>2
  • 3-5 ==> (3+7)%12 = 10 ==>-2

  表格修改后，每次计算完都在表格中进行对照，这样操作统一，得到的值也是正确的了。其实在计算机内部，补码的用处就是构造这张映射表的。

发表于 更新于 分类于
本文字数： 1.8k

git安装

git手册提供了完整的安装步骤。

安装成功后，命令行输入git命令可以检查是否安装成功：

1
2
#查看git版本
git --version

最小配置

使用git之前需要配置user.name和user.email，可以方便绑定每次操作的用户信息。

1
2
$ git config --global user.name 'your_name'
$ git config --global user.email 'your_email@domain.com'

上面的'--global'是git的作用域，git一共有三个作用域：

  • --local :只对某个仓库有效
  • --global ：对当前用户的所有仓库有效
  • --system ：对系统的所有登录用户有效

显示config的配置，可以加--list：

1
2
3
$ git config --list --local
$ git config --list --global
$ git config --list --system

创建仓库并配置local用户信息

建立git仓库有两种使用场景：

第一种场景：把已经有的项目代码列入git管理

1
2
$ cd 项目代码目录
$ git init

 

第二种场景：新建的项目直接用git管理：

1
2
3
$ cd 某个目录
$ git init your_project  #会在当前路径下创建和项目名称同名的文件夹
$ cd your_project

 

以第二种方式为例，执行完命令后，会在目录下生成一个'.git'的隐藏目录。

如果此时在这个目录下配置local的用户名和邮箱，且和global配置的不同，那么在这个仓库中执行的操作会以local配置为准生效。

工作区和暂存区

1
2
3
$ git add files  #把工作目录中的内容添加暂存区

$ git commit     #把暂存区中的内容添加到正式版本历史

git标准的操作是每次在工作目录中修改的文件，都先添加入暂存区。为了某个功能而做的修改都添加入暂存区后，可以统一把这批文件commit到git版本库中。

1
2
3
4
$ git reset --hard
#这个命令可以重置暂存区，轻易不要使用

$ git status #查看工作目录修改状态

 

如果想要在git中修改某个文件的文件名，可以有两种方式：

1
2
3
4
5
6
7
8
# 方式1：工作目录中修改文件名，然后重新add、commit
$ mv old new   #修改文件名
$ git add new
$ git commit

# 方式2：直接调用git命令
$ git mv old new
$ git commit

查看版本历史和分支

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 查看每次提交的细节
$ git log

# 只查看提交备注
$ git log --oneline

# 只查看最近的某几次提交
$ git log -n2 --oneline  #只查看2次

# 查看本地有多少分支
$ git branch -v

# 查看所有分支的提交记录
$ git log --all

# 图形化查看所有分支的提交记录
$ git log --all --graph

 

对于Windows用户来说，可能更习惯图形化操作，可以使用git自带的图形化工具：

1
$ gitk  # 打开图形化界面

".git"目录

新建仓库后，工作目录下会生成一个隐藏的".git"目录，这里面就是git最核心的内容。

常用的文件如下：

  • HEAD文件：记录当前工作在哪个分支上；
  • config文件：当前工作目录的一些配置，比如user.name和user.email；
  • refs/heads目录：各个分支指向的提交hash；
  • refs/tags目录：各个tag指向的提交hash；
  • objects目录：存放文件和更改，内部的对象可以分为commit、tree和blob三种类型；这个是git版本管理的底层目录；

git文件类型（commit、tree和blob）

  数据存储是git的核心技术点；git的目标是项目管理，而项目管理中的文件变更很频繁，如果没有一个好的数据管理技术，git的存储信息会越来越大，性能会越来越差。所以设计一个良好的数据存储机制是很关键的。

  .git的object中就是git存储的核心目录，下面的文件共有三种类型：commit、tree和blob。

  上图是git官网文档的实例，每次执行commit操作都会创建一个commit对象出来；一个commit对应唯一一棵树，是这个commit的快照，存放所有的文件夹和文件；blob就是其中具体的文件；要注意每个blob和文件名毫无关系，在git中只要这个文件的内容相同，那对应的就是一个blob，这样可以大大减少存储代价。