小笔记

1. 时间复杂度练习#

1. 默写 O(n) 的递归快速幂、默写 O(logn) 的递归快速幂，找到区别。

   1
   #include <bits/stdc++.h>
   2
   #define ll long long
   3
   using namespace std;
   4
   
   5
   /* O(n)的递归快速幂 */
   6
   ll bad_qpow(ll x,ll n){
   7
     if(!(n-1)) return x;
   8
     return bad_qpow(x,n/2)*bad_qpow(x,n/2)*(n%2?x:1);
   9
   }
   10
   
   11
   /* O(logn)的递归快速幂 */
   12
   ll good_qpow(ll x,ll n){
   13
     if(!(n-1))return x;
   14
     ll res=good_qpow(x,n/2);
   15
     return res*res*(n%2?x:1);
   16
   }
   17
   
   18
   /* O(logn)的递归快速幂，且常数更优 */
   19
   ll best_qpow(ll x,ll n){
   20
     ll base=x,res=1;
   21
     while(n){
   22
       if(n&1){
   23
         res*=base;
   24
       }
   25
       base*=base;
   26
       n>>=1;
   27
     }
   28
     return res;
   29
   }
   30
   
   31
   ll x,n;
   32
   
   33
   int main(){
   34
     cin>>x>>n;
   35
     cout<<bad_qpow(x,n)<<endl;
   36
     cout<<good_qpow(x,n)<<endl;
   37
     cout<<best_qpow(x,n)<<endl;
   38
     return 0;
   39
   }

   展开收起

   区别： $O(n)$ 的快速幂将函数分治后又调用了两次，算了两次相同的值，相当于没优化；而 $O(logn)$ 的快速幂利用空间换时间，把得数保存下来再乘两次。

2. O(nlogn) 的归并排序和 O(n) 的递归快速幂复杂度区别在哪里。

   归并排序：

   1
   void MergeSort(int* arr,int left,int right,int* s){//归并排序递归
   2
     if(right-left<=1){//元素个数小于1，直接返回
   3
       return;
   4
     }
   5
     int mid=left+(right-left)/2;
   6
     MergeSort(arr,left,mid,s);//归并左半部分
   7
     MergeSort(arr,mid,right,s);//归并右半部分
   8
     MergeData(arr,left,mid,right,s);//将当前有序的序列进行归并
   9
     memcpy(arr+left,s+left,sizeof(arr[0])*(right-left));//将归并后的将结果拷贝回原来的数组，为下次归并做准备
   10
   }

   可以看到，对于每一层，不管怎么分治，最终均摊下来每一个元素都要走到；而每次对半分，最多可以分 $logn$ 层。所以总复杂度为 $O(logn)$ 。

   而 $O(n)$ 的递归快速幂虽然也是每次对半分，但是它只是对一个数字进行对半分，并没有遍历什么数组，所以最终的复杂度应该是最后一层每次 return x ，返回了 $n$ 遍。

3. 程序阅读第二题订正时间复杂度、说明什么时候是 O(n) 什么时候是 O(nlogn)

   注意原代码：

   1
   void dfs(...){
   2
     ...
   3
     if(...){
   4
       return dfs(...n/2...);
   5
     }else if(...){
   6
       return dfs(...n/2...);
   7
     }else{
   8
       ...
   9
     }
   10
   }

   注意这里有 if...else... 的关系，所以两个 dfs 不会同时执行，而回只执行一个。那么执行次数就是 $n+n/2+n/4+n/8+...+1=2*n$ ，即时间复杂度为 $O(n)$ 。

   如果没有 if...else... ，则每次两个 dfs 都会执行，每层复杂度 $O(n)$ ，共 $logn$ 层，此时总复杂度为 $O(nlogn)$ 。

2. 错题总结#

1. 大规模集成电路的出现，推动了个人计算机的诞生。
2. 一个汉字占两倍的英文字符长度。
3. 5双手套5种颜色，先从5种颜色里选出3种，C(5,3), 对于每一种颜色的手套还可选(左手套和右手套不一样)，对于每种颜色有2种，三种颜色有8种，所以总共80种。

3. 组合数学难题#

$5$ 双手套，拿三只，恰有一双匹配，方案数多少？（左右有区别）

先选出一个完整的颜色， $C(5,3)=10$ ，再在剩下的所有手套中选出1个， $C(8,1)=8$ 。所以总方案为 $80$ 。