看动画轻松理解时间复杂度(二)

看动画轻松理解时间复杂度(二)

点击上方“简说Python”,选择“置顶/星标公众号”

福利干货,第一时间送达!

www.zeeklog.com  - 看动画轻松理解时间复杂度(二)

本文转载自公众号 | 程序员小吴

作者 | 程序员小吴

【作者简介】

程序员小吴,一个致力于用动画图解数据结构的程序员。LeetCodeAnimation作者,GitHub一万,连续一月占据Trending榜榜首。

上篇文章讲述了与复杂度有关的大 O 表示法和常见的时间复杂度量级,这篇文章来讲讲另外几种复杂度: 递归算法的时间复杂度(recursive algorithm time complexity),最好情况时间复杂度(best case time complexity)、最坏情况时间复杂度(worst case time complexity)、平均时间复杂度(average case time complexity)和均摊时间复杂度(amortized time complexity)。

递归算法的时间复杂度

如果递归函数中,只进行一次递归调用,递归深度为depth;

在每个递归的函数中,时间复杂度为T;

则总体的时间复杂度为O(T * depth)

在前面的学习中,归并排序 与 快速排序 都带有递归的思想,并且时间复杂度都是O(nlogn) ,但并不是有递归的函数就一定是 O(nlogn) 级别的。从以下两种情况进行分析。

① 递归中进行一次递归调用的复杂度分析
二分查找法
www.zeeklog.com  - 看动画轻松理解时间复杂度(二)
 1int binarySearch(int arr[], int l, int r, int target){
 2    if( l > r ) return -1;
 3
 4    int mid = l + (r-l)/2; 
 5    if( arr[mid] == target ) return mid;  
 6    else if( arr[mid] > target ) 
 7    return binarySearch(arr, l, mid-1, target);    // 左边 
 8    else
 9    return binarySearch(arr, mid+1, r, target);   // 右边
10}

比如在这段二分查找法的代码中,每次在 [ l ,  r  ] 范围中去查找目标的位置,如果中间的元素 arr[mid] 不是 target,那么判断 arr[mid]是比 target 大 还是 小 ,进而再次调用 binarySearch这个函数。

在这个递归函数中,每一次没有找到target时,要么调用 左边 的 binarySearch函数,要么调用 右边 的 binarySearch函数。也就是说在此次递归中,最多调用了一次递归调用而已。根据数学知识,需要log2n次才能递归到底。因此,二分查找法的时间复杂度为 O(logn)。

求和
www.zeeklog.com  - 看动画轻松理解时间复杂度(二)
1int sum (int n) {
2  if (n == 0) return 0;
3  return n + sum( n - 1 )
4}

在这段代码中比较容易理解递归深度随输入 n 的增加而线性递增,因此时间复杂度为 O (n)。

求幂
www.zeeklog.com  - 看动画轻松理解时间复杂度(二)
1//递归深度:logn
2//时间复杂度:O(logn)
3double pow( double x, int n){
4  if (n == 0) return 1.0;
5
6  double t = pow(x,n/2);
7  if (n %2) return x*t*t;
8  return t * t;
9}

递归深度为 logn,因为是求需要除以 2 多少次才能到底。

② 递归中进行多次递归调用的复杂度分析

递归算法中比较难计算的是多次递归调用。

先看下面这段代码,有两次递归调用。

1// O(2^n) 指数级别的数量级,后续动态规划的优化点
2int f(int n){
3 if (n == 0) return 1;
4 return f(n-1) + f(n - 1);
5}
www.zeeklog.com  - 看动画轻松理解时间复杂度(二)

递归树中节点数就是代码计算的调用次数。

比如 当 n = 3 时,调用次数计算公式为

1 + 2 + 4 + 8 = 15

一般的,调用次数计算公式为

2^0 + 2^1 + 2^2 + …… + 2^n
www.zeeklog.com  - 看动画轻松理解时间复杂度(二)

与之有所类似的是 归并排序 的递归树,区别点在于

  • 1. 上述例子中树的深度为 n,而 归并排序 的递归树深度为logn
  • 2. 上述例子中每次处理的数据规模是一样的,而在 归并排序 中每个节点处理的数据规模是逐渐缩小的

因此,在如 归并排序 等排序算法中,每一层处理的数据量为 O(n) 级别,同时有 logn 层,时间复杂度便是 O(nlogn)。

最好、最坏情况时间复杂度

www.zeeklog.com  - 看动画轻松理解时间复杂度(二)


最好、最坏情况时间复杂度指的是特殊情况下的时间复杂度。

动图表明的是在数组 array 中寻找变量 x 第一次出现的位置,若没有找到,则返回 -1;否则返回位置下标。

1int find(int[] array, int n, int x) {
2  for (  int i = 0 ; i < n; i++) {
3    if (array[i] == x) {
4        return i;
5        break;
6    }
7  }
8  return -1;
9}

在这里当数组中第一个元素就是要找的 x 时,时间复杂度是 O(1);而当最后一个元素才是 x 时,时间复杂度则是 O(n)。

最好情况时间复杂度就是在最理想情况下执行代码的时间复杂度,它的时间是最短的;最坏情况时间复杂度就是在最糟糕情况下执行代码的时间复杂度,它的时间是最长的。

平均情况时间复杂度

最好、最坏时间复杂度反应的是极端条件下的复杂度,发生的概率不大,不能代表平均水平。那么为了更好的表示平均情况下的算法复杂度,就需要引入平均时间复杂度。

平均情况时间复杂度可用代码在所有可能情况下执行次数的加权平均值表示。

还是以 find 函数为例,从概率的角度看, x 在数组中每一个位置的可能性是相同的,为 1 / n。那么,那么平均情况时间复杂度就可以用下面的方式计算:

((1 + 2 + … + n) / n + n)  /  2 = (3n + 1) / 4

find 函数的平均时间复杂度为 O(n)。

均摊复杂度分析

我们通过一个动态数组的 push_back 操作来理解 均摊复杂度

www.zeeklog.com  - 看动画轻松理解时间复杂度(二)
 1template <typename T>
 2class MyVector{
 3private:
 4    T* data;
 5    int size;       // 存储数组中的元素个数
 6    int capacity;   // 存储数组中可以容纳的最大的元素个数
 7    // 复杂度为 O(n)
 8    void resize(int newCapacity){
 9        T *newData = new T[newCapacity];
10        for( int i = 0 ; i < size ; i ++ ){
11              newData[i] = data[i];
12            }
13        data = newData;
14        capacity = newCapacity;
15    }
16public:
17    MyVector(){
18        data = new T[100];
19        size = 0;
20        capacity = 100;
21    }
22    // 平均复杂度为 O(1)
23    void push_back(T e){
24        if(size == capacity)
25            resize(2 * capacity);
26        data[size++] = e;
27    }
28    // 平均复杂度为 O(1)
29    T pop_back(){
30        size --;
31        return data[size];
32    }
33
34};

push_back实现的功能是往数组的末尾增加一个元素,如果数组没有满,直接往后面插入元素;如果数组满了,即 size == capacity ,则将数组扩容一倍,然后再插入元素。

例如,数组长度为 n,则前 n 次调用 push_back 复杂度都为 O(1) 级别;在第 n + 1 次则需要先进行 n 次元素转移操作,然后再进行 1 次插入操作,复杂度为 O(n)。

因此,平均来看:对于容量为 n 的动态数组,前面添加元素需要消耗了 1 * n 的时间,扩容操作消耗  n 时间 ,总共就是 2 * n 的时间,因此均摊时间复杂度为 O(2n / n) = O(2),也就是 O(1) 级别了。

可以得出一个比较有意思的结论:一个相对比较耗时的操作,如果能保证它不会每次都被触发,那么这个相对比较耗时的操作,它所相应的时间是可以分摊到其它的操作中来的。

|今日打卡主题

请看今日头条推文,并打卡,谢谢。

| 推荐阅读

右下角点个「好看」就行啦,比心!!!

www.zeeklog.com  - 看动画轻松理解时间复杂度(二)

2019,我们一起让知识『好看

Read more

使用本地大模型调用代码,根本就是一场骗局!

使用本地大模型调用代码,根本就是一场骗局!

通过大模型调用其他工具到底可不可行?ChatGPT 或许能轻松搞定一切,但同样的需求落在本地大模型上,恐怕就要打个问号了。 法国开发工程师 Emilien Lancelot 尝试了多款号称具备工具调用功能的 agent 框架,来看看本地大模型到底能不能完成任务,但结果就像他总结的“一无所获”。是什么让这位工程师失望了? 用 AutoGPT,得会点“糊弄学” AutoGPT 是款貌似强大的框架,提供很酷的 CLI 外加 Flutter UI,能够通过浏览器创建 agent。其主要功能是处理用户的文档、音频、视频等本地内容。 但是……它主要依靠 ChatGPT 或其他专有大模型服务来完成繁重工作,至少给我们的感觉是如此。 我们必须“唬弄”AutoGPT 才能使用 Ollama 端点,让其误认为是 ChatGPT。 ## OPENAI_API_KEY - OpenAI API

By Ne0inhk
详细说明Encoder-only架构的特点以及他和encoder decoder的区别和联系

详细说明Encoder-only架构的特点以及他和encoder decoder的区别和联系

Poe Encoder-only 架构的特点 Encoder-only 模型只使用 Transformer 的编码器部分,专注于对输入序列的理解和表征学习。这类模型通常被用在需要对输入文本进行深度理解的任务上,如文本分类、问答和语义匹配。以下是 Encoder-only 架构的核心特点: 1. 双向上下文建模 * 特点:Encoder-only 模型通过自注意力机制(Self-Attention)同时关注输入序列的前后文。 * 优势:相比单向模型(如 Decoder-only),它可以更全面地捕捉输入序列的全局语义,适合需要理解复杂上下文的任务。 * 实现方式:在训练过程中,不对输入序列进行因果掩码(Causal Masking),允许模型在任何位置访问序列的所有位置。 * 例子:BERT 的 Masked Language Model(MLM)训练任务通过随机遮盖部分单词,依赖左侧和右侧的信息来预测被遮盖的词,即双向建模的典型体现。 2. 适用于理解任务 * 特点:Encoder-only 模型专注于理解输入序列,而不生成输出序列,因此适合处理分类、

By Ne0inhk
手把手教学,DeepSeek-R1微调全流程拆解

手把手教学,DeepSeek-R1微调全流程拆解

手把手教学,DeepSeek-R1微调全流程拆解 原创 极客见识  2025年02月09日 09:02 广东 DeepSeek 通过发布其开源推理模型 DeepSeek-R1 颠覆了 AI 格局,该模型使用创新的强化学习技术,以极低的成本提供与 OpenAI 的 o1 相当的性能。 更令人印象深刻的是,DeepSeek 已将其推理能力提炼成几个较小的模型。这篇文章,我们将使用其蒸馏版本之一引导大家完成 DeepSeek-R1 的整个微调过程。 本文章将演示了如何微调其中一个模型(使用我们自己的自定义思维链数据集),然后保存和部署微调后的模型。 高级推理模型微调 DeepSeek 简介 DeepSeek-R1 是由深度求索(DeepSeek)公司开发的突破性推理模型。DeepSeek-R1 基于 DeepSeek-V3-Base(总共 671B 个参数,每次推理 37B 处于活动状态)构建,使用强化学习 (RL) 在提供最终答案之前生成思路链

By Ne0inhk