数据结构学习笔记——第一章:绪论(上)

一、目标:计算

  整个计算机科学的目的,都是为了实现高效和低耗的计算。为了理解什么是计算,我们首先来看几个实例。


Fig. 1 实例:绳索计算
Fig. 2 实例:尺规计算机
1.1 定义算法

  计算,就是借助某种工具,遵照一定规则,以明确而机械的形式进行。计算模型(计算机)就是计算中使用的工具。
  算法,即在特定计算模型下,旨在解决特定问题的指令序列。

  • 特点:

①输入、输出明确
②正确性(可解决问题)
③确定性(任意算法都可描述为一个由基本操作注组成的序列)
④可行性 (每一基本操作都可实现)
⑤有穷性 (对于任何输入,经过有穷次计算后终止)


  • 如何理解”有穷性“?
    Fig. 3 Hailstone序列

    例子:
    Hailstone(42) = \{42, 21, 64, 32, ..., 1 \rbrace
    Hailstone序列一定会呈现出整体下降的趋势,尽管中间可能会飘忽不定。
#include<iostream>

int len_hailstone(int n){
    int length = 0;
    std::cout<<n<<", ";
    while(n>1){(n%2) ? n=n*3+1 : n/=2;std::cout<<n<<", "; length++;}
    std::cout<<std::endl;
    return length;
}

int main(int argc, char* argv[]){
    auto n = atoi(argv[1]);
    std::cout<<"length of hailstone("<<n<<"): "<<len_hailstone(n)<<std::endl;
    return 0;
}
➜  Chapter1 ./hailstone 27     
27, 82, 41, 124, 62, 31, 94, 47, 142, 71, 214, 107, 322, 161, 484, 242, 121, 364, 182, 91, 274, 137, 412, 206, 103, 310, 155, 466, 233, 700, 350, 175, 526, 263, 790, 395, 1186, 593, 1780, 890, 445, 1336, 668, 334, 167, 502, 251, 754, 377, 1132, 566, 283, 850, 425, 1276, 638, 319, 958, 479, 1438, 719, 2158, 1079, 3238, 1619, 4858, 2429, 7288, 3644, 1822, 911, 2734, 1367, 4102, 2051, 6154, 3077, 9232, 4616, 2308, 1154, 577, 1732, 866, 433, 1300, 650, 325, 976, 488, 244, 122, 61, 184, 92, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1, 
length of hailstone{27}: 111
  • 问题:对于任意n, 序列的长度是否是有穷的?
  • 答案:不确定。这个序列的长度未必是有限的。因此上面的程序未必可以称为一个“算法”。

  • 什么是好算法
      对算法来说最重要的特征:效率
    Algorithms + Data Structures (DSA) = Programs
1.2 计算模型

  如何评价不同DSA的效率: 度量。 ( If you cannot measure it, you can not improve it. )

  • 测度:


    Fig. 5 用某个实例的计算成本来评价DSA的效率是不现实的
  • 分析:问题实例的规模,往往是决定计算成本的主要因素(正相关)
  • 最坏情况分析原则:对于规模为n的所有实例中,只关注最坏(成本最高)者
1.2.1 图灵机模型
Fig. 6 图灵机概念
  • 实例:通过图灵机完成非负整数加一的功能。


    Fig. 7
1.2.2 RAM模型
Fig. 8. RAM模型及其指令集
  • 重点:这些模型将算法的运行时间转换为基本操作的次数来评价,从而将DSA的评价和单次实验的各种环境因素分离开。具体来说,每个算法的流程应该是清晰、可罗列,且没有歧义的。这就为评价算法提供了基础。

二、复杂度分析

2.1 大O记号

  大O记号可以看做评价DSA的一把直尺,其刻度并不精细,而是主要用于评价DSA的“潜力”,比如它在求解大规模问题时的性能。更确切的说,大O记号关注的是随着n的增长(n>>2),算法成本的增长趋势。

Fig. 9. 大O记号

  大O记号的处理手法:

  1. 常系数可忽略
  2. 低次项可忽略
2.1.1 常数复杂度O(1)

   2 = 2013 = 2013^{2013} = O(1)。这类算法的效率最高。

2.1.2 对数复杂度O(log^n)

常底数和常数次幂无所谓:
  ①log_a^n = log_a^b * log_b^n = O(log^n)
  ②{logn}^c = c*log^n = O(log^n)

  • 这类算法无限接近于O(1 ),非常令人满意。
2.1.3 多项式复杂度 O(n^c)

  多项式的最高此项即为复杂度O(n^k)

  • 线性复杂度: O(n): 代表线性函数。很多编程题复杂度都介乎O(n)-O(n^2)
2.1.4 指数复杂度 O(2^n)

  这类算法的计算成本增长的极快,通常认为是不可忍受的。
  对任意c > 1, n^c = O(2^n) //证明: e^n = 1 + n + n^2/2! + n^3/3!
  n^{1000}=O(1.0000001^n) = O(2^n)

Fig. 10. 从多项式复杂度到指数复杂度

2.2 实例: Subset
Fig. 11 实例:Subset问题
  • 这个问题如果没有其他约束条件,最优的算法就是逐一枚举所有可能的子集,再统计其中元素的和。其复杂度为2^n
  • Subset问题是一个NP-complete问题。

三、算法分析

  两个主要任务: 正确性 + 复杂度。


Fig. 12 算法分析:前提与方法
3.1 级数
  • 算数级数: T(n) = 1 + 2 + ... + n = O(n^2)
  • 幂方级数: 1^k + 2^k + 3^k + ... + n^k = O(n^{k+1}) # 比幂次高一级
  • 几何级数: a^0 + a^1 + a^2 + ... + a^n = O(a^n)
    常用: 2^0 + 2^1 + 2^2 + ... + 2^n = O(2a^n)
  • 收敛级数
  • 其他常见级数:
    ①调和级数 h(n) = 1 + 1/2 + ... + 1/n = O(logn)
    ②对数级数: log 1 + log2 + ... + logn = O(nlogn)
3.1 循环 vs. 级数
  • 二重循环:
    ①两个控制变量之间没有耦合: 复杂度为O(n^2)
for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
        O(1)_Operation(i, j)  

②两个控制变量之间存在耦合: 复杂度也是O(n^2)

for (int i = 0; i < n; i++)
    for (int j = 0; j < i; j++)
        O(1)_Operation(i, j)  

Fig. 13 二重循环复杂度

③注意下面的循环复杂度为

for (int i = 0; i < n; i++)
    for (int j = 0; j < i; j+=j)
        O(1)_Operation(i, j)  
3.2 实例:非极端排序
  • 问题:给定整数子集S,|S| = n>=3,找出元素a,确保a既不是S的最大值也不是最小值。
  • 解:只需要从S中任取三个元素,然后找出这三个元素中的非极端元素即可。
  • 说明: 某些情况下无论问题的规模多大,算法需要执行的时间不变:


    Fig. 14 非极端排序复杂度
3.3 实例:冒泡排序
Fig. 15 冒泡排序
vector<int> bubble_naive(vector<int> vec){
    int steps=0;
    int n = vec.size();
    for (int i=0; i<n; ++i){
            // No out of range error will be reported in cpp.
            for (int j=0; j<n-1; ++j){
                if (vec[j] > vec[j+1]){
                    swap(vec[j], vec[j+1]);
                }
                ++steps;
            }

        }
    cout<< "Steps: "<<steps<<endl;
    return vec;
}

vector<int> bubble_optimized(vector<int> vec){
    int steps=0;
    int n = vec.size();
    for (int i=n; i>0; --i){
            for (int j=0; j<i-1; ++j){
                if (vec[j] > vec[j+1]){
                    swap(vec[j], vec[j+1]);
                }
                ++steps;
            }
        }
    cout<< "Steps: "<<steps<<endl;
    return vec;
}

vector<int> bubble_optimized2(vector<int> vec){
    int steps=0;
    int n = vec.size();
    for (int i=n; i>0; --i){
        bool swapped = false;
        for (int j=0; j<i-1; ++j){
            if (vec[j] > vec[j+1]){
                swap(vec[j], vec[j+1]);
                swapped = true;
            }
            ++steps;
        }
        if (!swapped){
            cout<< "Break! Steps: "<<steps<<endl;
            return vec;
        }

    }
    cout<< "Steps: "<<steps<<endl;
    return vec;
}
// =======================

void main(){
    //vector<int> vec = {1,4,2,3,5,8,9,7,0};
    vector<int> vec = {1,2,4,3,5,6,7,8,9,22,0,11,12,3};
    print(vec);
    cout<<endl;
    auto vec1=bubble_naive(vec);
    auto vec2=bubble_optimized(vec);
    auto vec3=bubble_optimized2(vec);
    print(vec1);
    print(vec2);
    print(vec3);
}

  • Output:
Steps: 182
Steps: 91
Break! Steps: 88
0, 1, 2, 3, 3, 4, 5, 6, 7, 8, 9, 11, 12, 22,
0, 1, 2, 3, 3, 4, 5, 6, 7, 8, 9, 11, 12, 22,
0, 1, 2, 3, 3, 4, 5, 6, 7, 8, 9, 11, 12, 22,

四、迭代与递推

4.1 减而治之

  所谓“减而治之”,就是讲一个复杂的问题划分成两部分,其中一部分是

Fig. 16 减而治之
4.2 Max2问题
Fig. 16 迭代解法一
  • 迭代解法二:初始化两个指针(下标索引)并确定其顺序。从第三个元素开始扫描,每次扫描先将当前下标元素和x2位置数值(较小的元素)进行比较,若大于x2,则x2的下标更新为当前下标,同时和x1进行比较。


    Fig. 17. 迭代解法二
  • 迭代解法二的最好情况需要n-1次比较;最坏情况需要2n-3次比较,并没有实质性的改善。
  • 这个算法体现出分而治之思想的优点。下面使用二分法,每次将数组均分成两段,分别找出第一段(L)的max2元素X1L, X2L和第二段(R)的max2元素X1R, X2R,然后操作为:将X1L于X1R进行比较确定全局最大值(如X1L > X1R),那么再将X2L和X1R进行比较确定次大值。


    Fig. 18 二分递归
#include<iostream>
#include<vector>
using namespace std;

//vector A: [lo, lo+1, lo+2, ..., hi)
void max2(vector<int> A, int lo, int hi, int &x1, int& x2){
    if (hi - lo == 3) {
        if (A[lo] < A[lo+1]){
            if (A[lo+1]<A[lo+2]) {
                x1=lo+2;
                x2=A[lo+1]>A[lo]?lo+1:lo;
            } else {
                x1=lo+1;
                x2=A[lo+2]>A[lo]?lo+2:lo;};
        }
        else { // lo > lo+1
            if (A[lo]>A[lo+2]) {
                x1=lo;
                x2=A[lo+1]>A[lo+2] ? lo+1:lo+2;
            } else {
                x1=lo+2;x2=A[lo+1]>A[lo]?lo+1:lo;
            }
        }
        return;
    }  //T(3)<=3;

    if (hi - lo == 2) {
        if (A[lo]>A[hi-1]){
            x1 = lo;
            x2 = hi-1;
        } else {
            x1 = hi-1;
            x2 = lo;
        }
        return;
    }
    int mi = (lo + hi) / 2;
    int X1L, X2L; max2(A, lo, mi, X1L, X2L);
    int X1R, X2R; max2(A, mi, hi, X1R, X2R);
    if (A[X1L] > A[X1R]){
        x1 = X1L;
        x2 = A[X2L] > A[X1R] ? X2L : X1R;
    }
    else{
        x1 = X1R;
        x2 = A[X2R] > A[X1L] ? X2R : X1L;
    }
}

int main(){
    vector<int> A={1,3,4,0,9,-2,8,11};
    //vector<int> A={5,6};
    int lo = 0;
    int hi = A.size();
    int x1, x2;
    max2(A, lo, hi, x1, x2);
    cout<<"Max 2 number: "<< A[x1]<<", "<<A[x2]<<endl;
}


龙哥系统组常用面试题目:

  • 连续子数组的和 (动态规划)
  • 二维数组向右或者向下走,选择和最大的路径 (动态规划)
  • 立方体八个顶点,一个点给一个数,问能否实现每个面四个顶点和相等 (动态规划/全排列,了解下)
  • 求一个数组中最大的K个数 (堆排序 /c++ map 平衡二叉树)
  • 背包问题
  • 长度为n-1的数组中存放了1-n之间的n-1个数。找到缺失的数
  • 二维数组从左往右从上往下递增,判断给定的数是否在数组中,若在则返回位置 (时间复杂度要求M+N)
  • 找出链表中环的位置/链表的删除和插入
  • 字符串处理: 将字符串中的某个字符替换为指定字符串(不含目标字符)
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 221,888评论 6 515
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 94,677评论 3 399
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 168,386评论 0 360
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 59,726评论 1 297
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 68,729评论 6 397
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 52,337评论 1 310
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 40,902评论 3 421
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 39,807评论 0 276
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 46,349评论 1 318
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 38,439评论 3 340
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 40,567评论 1 352
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 36,242评论 5 350
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 41,933评论 3 334
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 32,420评论 0 24
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 33,531评论 1 272
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 48,995评论 3 377
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 45,585评论 2 359