如果您想了解如何理解Kademlia节点操作的时间复杂度和kafka节点数的知识，那么本篇文章将是您的不二之选。我们将深入剖析如何理解Kademlia节点操作的时间复杂度的各个方面，并为您解答kafk

如果您想了解如何理解Kademlia节点操作的时间复杂度和kafka节点数的知识，那么本篇文章将是您的不二之选。我们将深入剖析如何理解Kademlia节点操作的时间复杂度的各个方面，并为您解答kafka节点数的疑在这篇文章中，我们将为您介绍如何理解Kademlia节点操作的时间复杂度的相关知识，同时也会详细的解释kafka节点数的运用方法，并给出实际的案例分析，希望能帮助到您！

• 如何理解Kademlia节点操作的时间复杂度（kafka节点数）
• 002-数据结构之算法的时间复杂度和空间复杂度
• 1-07Python列表与字典操作的时间复杂度
• C语言 超详细讲解算法的时间复杂度和空间复杂度
• C语言算法的时间复杂度和空间复杂度

如何理解Kademlia节点操作的时间复杂度（kafka节点数）

我现在正在通过阅读经典论文Kademlia：基于XOR度量的对等信息系统来学习Kademlia网络。我想了解其操作的复杂性，但仍然无法弄清楚。

在 3证明草图 部分中，本文给出了两个定义：

1. 节点深度（h） ：160 − i，其中i是非空桶的最小索引
2. 节点y在节点x中的存储桶高度 ：x将插入y的存储桶的索引减去x的 最低有效空存储桶 的索引。

还有三个结论：

1. 对于具有n个节点的系统，以给定的概率，任何给定节点的高度都将在 log n 的常数之内。
2. 在第k个最接近的节点中，最接近ID的节点的存储区高度可能在 log k 的常数之内。
3. 如果该节点的h个 最重要的k个桶 中没有一个为空，则查找过程将在每个步骤中找到一个接近一半的节点（或者距离更短一点），从而以 h-log k个 步骤打开该节点。

所以我的问题是：

1. 什么是 “最低有效空桶” 和 “最高有效k桶” ？
2. 如何以视觉方式解释 深度 和 铲斗高度 ？
3. 如何理解第二个和第三个结论，例如，为什么 log k 和 h-log k ？

答案1

自从我真正阅读本文以来已经有一段时间了，所以我主要是从我的实施经验中将它们拼凑在一起，而不是尝试将我头脑中的概念与本文的正式定义相匹配，因此请采用再加一点盐

什么是“最低有效空桶”和“最高有效K桶”？

这基本上是指按相对于节点自身ID的XOR距离排序的存储桶

如何以视觉方式解释深度和铲斗高度？

每个存储桶覆盖一个键空间区域。例如，对于键空间的1/16，从0x0000 简化为2个字节到0x0FFF。这可以用类似于CIDR的掩码0x0 /
4（4个前缀位）表示。那或多或少是一个桶的深度。

有几种组织路由表的方法。“正确”的方法是根据存储桶代表的最低ID将其表示为树或排序列表。这种方法允许进行任意的桶拆分操作，这是某些路由表优化所要求的，也可以用于实现节点多宿主。

简化的实现可以改为使用固定长度的数组，并将每个存储桶放置在相对于节点自己的ID的共享前缀位的位置。也就是说，数组中的位置0将具有0个共享的前缀位，这是最远的存储桶，该存储桶覆盖了键空间的50％，而存储桶中最高有效位是节点自身ID的反向MSB。

在那种情况下，深度就是数组的位置。

如何理解第二个和第三个结论，例如，为什么选择log k和h-log k？

假设您正在寻找距离您自己节点的ID最远的ID。这样，您将只有一个存储桶覆盖键空间的该部分，即它将覆盖键空间的一半，并且最高有效位与您的不同。因此，您从该存储桶中询问一个（或几个）节点。由于其ID位与您的查找目标具有相同的第一位，因此它们或多或少地保证将其分成两个或多个，即，至少具有目标空间的键空间覆盖率的两倍。因此，他们可以提供至少1位更好的信息。

当您查询更靠近目标的节点时，它们还将在目标区域附近具有更好的键空间覆盖范围，因为这也更接近其自己的节点ID。

冲洗，重复直到找不到更近的节点。

由于每个跃点一次至少可减少1位距离，因此您基本上需要一个O（log（n））跃点计数，其中n是网络规模。由于网络大小基本上决定了节点之间的平均距离，因此也决定了家用存储桶所需的存储桶深度。

如果目标密钥更接近您自己的ID，则您将需要较少的步骤，因为您将更好地覆盖密钥空间的该区域。

由于 k 是一个常数（每个桶的节点数），因此 log k
也是一个常数。将存储桶中的节点数增加一倍，它将具有给定键空间区域的两倍分辨率，因此（概率）将产生一个比k /
2大小的存储桶更接近目标一点的节点。也就是说，对于每个希望保存的跃点，每增加一个比特，就必须使每个存储桶的条目数增加一倍。

编辑：这是一个实际的单宿主bittorrent DHT路由表的可视化，按其前缀排序，即不相对于本地节点ID：

Node ID: 2A631C8E 7655EF7B C6E99D8A 3BF810E2 1428BFD4buckets: 23 / entries: 173000...   entries:8 replacements:800100...   entries:8 replacements:00010100...   entries:8 replacements:20010101000...   entries:8 replacements:400101010010...   entries:8 replacements:7001010100110000...   entries:8 replacements:30010101001100010...   entries:8 replacements:300101010011000110000...   entries:8 replacements:1001010100110001100010...   entries:3 replacements:00010101001100011000110...   entries:6 replacements:00010101001100011000111...   entries:6 replacements:00010101001100011001...   entries:8 replacements:2001010100110001101...   entries:8 replacements:100101010011000111...   entries:8 replacements:200101010011001...   entries:7 replacements:00010101001101...   entries:8 replacements:0001010100111...   entries:8 replacements:0001010101...   entries:8 replacements:100101011...   entries:7 replacements:0001011...   entries:8 replacements:00011...   entries:8 replacements:801...   entries:8 replacements:81...   entries:8 replacements:8

002-数据结构之算法的时间复杂度和空间复杂度

一、概述

　　对于同一个问题来说，可以有多种解决问题的算法。尽管算法不是唯一的，但是对于问题本身来说相对好的算法还是存在的，这里可能有人会问区分好坏的标准是什么？这个要从「时效」和「存储」两方面来看。

　　好的算法应该具备时效高和存储低的特点。这里的「时效」是指时间效率，也就是算法的执行时间，对于同一个问题的多种不同解决算法，执行时间越短的算法效率越高，越长的效率越低；「存储」是指算法在执行的时候需要的存储空间，主要是指算法程序运行的时候所占用的内存空间。

1.1、不同写法影响的算法

实现：1+2+…+99+100

算法一、

int i, sum = 0, n = 100;   // 执行1次
for( i=1; i <= n; i++ )    // 执行了n+1次
{
    sum = sum + i;          // 执行n次
}

算法二、

int sum = 0, n = 100;     // 执行1次
sum = (1+n)*n/2;          // 执行1次

第一种算法：执行了1+(n+1)+n=2n+2次。
第二种算法：是1+1=2次
如果我们把循环看做一个整体，忽略头尾判断的开销，那么这两个算法其实就是n和1的差距。

二、时间复杂度

2.1、算法效率的度量方法

2.1.1、事后统计方法

这种方法主要是通过设计好的测试程序和数据，利用计算机计时器对不同算法编制的程序的运行时间进行比较，从而确定算法效率的高低。

2.1.2、事前分析估算方法【推荐】

在计算机程序编写前，依据统计方法对算法进行估算。

经过总结，我们发现一个高级语言编写的程序在计算机上运行时所消耗的时间取决于下列因素：

1. 算法采用的策略，方案
2. 编译产生的代码质量
3. 问题的输入规模
4. 机器执行指令的速度

2.2、大O表示法

　　「数量级」函数用来描述当规模 n 增加时，T(n) 函数中增长最快的部分，这个数量级函数我们一般用「大 O」表示，记做 O(f(n))。它提供了计算过程中实际步数的近似值，函数 f(n) 是原始函数 T(n) 中主导部分的简化表示。　　

　　在上面的求和函数的那个例子中，T(n) = n + 1，当 n 增大时，常数 1 对于最后的结果来说越来不越没存在感，如果我们需要 T(n) 的近似值的话，我们要做的就是把 1 给忽略掉，直接认为 T(n) 的运行时间就是 O(n)。这里你一定要搞明白，这里不是说 1 对 T(n) 不重要，而是当 n 增到很大时，丢掉 1 所得到的近似值同样很精确。

　　再举个例子，比如有一个算法的 T(n) = 2n^2+ 2n + 1000，当 n 为 10 或者 20 的时候，常数 1000 看起来对 T(n) 起着决定性的作用。但是当 n 为 1000 或者 10000 或者更大呢？n^2 起到了主要的作用。实际上，当 n 非常大时，后面两项对于最终的结果来说已经是无足轻重了。与上面求和函数的例子很相似，当 n 越来越大的时候，我们就可以忽略其它项，只关注用 2n^2 来代表 T(n) 的近似值。同样的是，系数 2 的作用也会随着 n 的增大，作用变得越来越小，从而也可以忽略。我们这时候就会说 T(n) 的数量级 f(n) = n^2，即 O(n^2)。

2.3、最好情况、最坏情况和平均情况

　　某个特定的数据集能让算法的执行情况极好，这就是最「最好情况」，而另一个不同的数据会让算法的执行情况变得极差，这就是「最坏情况」。不过在大多数情况下，算法的执行情况都介于这两种极端情况之间，也就是「平均情况」。因此一定要理解好不同情况之间的差别，不要被极端情况给带了节奏。

　　对于「最优情况」，没有什么大的价值，因为它没有提供什么有用信息，反应的只是最乐观最理想的情况，没有参考价值。「平均情况」是对算法的一个全面评价，因为它完整全面的反映了这个算法的性质，但从另一方面来说，这种衡量并没有什么保证，并不是每个运算都能在这种情况内完成。而对于「最坏情况」，它提供了一种保证，这个保证运行时间将不会再坏了，**所以一般我们所算的时间复杂度是最坏情况下的时间复杂度**，这和我们平时做事要考虑到最坏的情况是一个道理。　　

2.4、各种数量级函数

　　对比表格

double max=a[0];
for(int i=1;i<N;i++)
　　if(a[i]>max)max=a[i];

for (int i = 0; i < N; i++) 
    for (int j = i+1; j < N; j++) 
        if(a[i]+a[j]==0)cnt++;

for (int i = 0; i < N; i++) 
    for (int j = i+1; j < N; j++)
        for (int k = j+1; k < N; k++) 
            if(a[i]+a[j]+a[k]==0)cnt++;

　　对比图

　　在上图中，我们可以看到当 n 很小时，函数之间不易区分，但是当 n 增大时，能看到很明显的区别

　　O(1) < O(logn) < O(n) < O(nlogn) < O(n²) < O(n³) < O(2ⁿ)<O(n!)

　　注：2=log₂(4)=log₃（9）=log₅（25）=lg100  

　　　　说明：log2(4) 其实是2²=4以2为底4的对数是2  ，lg 是指以10为底即log10，ln是以自然对数为底即loge(XX),其中e是一个无限不循环小数，其值约等于2.71828182845

 　　n!标识n的阶乘，n!=1*2*3…(n-2)*(n-1)*n，如0!=1,3!=1*2*3=6

　　Ο(1)表示基本语句的执行次数是一个常数，一般来说，只要算法中不存在循环语句，其时间复杂度就是Ο(1)。其中Ο(log₂n)、Ο(n)、 Ο(nlog₂n)、Ο(n²)和Ο(n³)称为多项式时间，而Ο(2ⁿ)和Ο(n!)称为指数时间。计算机科学家普遍认为前者（即多项式时间复杂度的算法）是有效算法，把这类问题称为P（Polynomial,多项式）类问题，而把后者（即指数时间复杂度的算法）称为NP（Non-Deterministic Polynomial, 非确定多项式）问题。

　　一般情况下，对一个问题（或一类算法）只需选择一种基本操作来讨论算法的时间复杂度即可，有时也需要同时考虑几种基本操作，甚至可以对不同的操作赋予不同的权值，以反映执行不同操作所需的相对时间，这种做法便于综合比较解决同一问题的两种完全不同的算法。

2.5、求解算法的时间复杂度

　　⑴ 找出算法中的基本语句；

　　算法中执行次数最多的那条语句就是基本语句，通常是最内层循环的循环体。

　　⑵ 计算基本语句的执行次数的数量级；

　　只需计算基本语句执行次数的数量级，这就意味着只要保证基本语句执行次数的函数中的最高次幂正确即可，可以忽略所有低次幂和最高次幂的系数。这样能够简化算法分析，并且使注意力集中在最重要的一点上：增长率。

　　⑶ 用大Ο记号表示算法的时间性能。

　　将基本语句执行次数的数量级放入大Ο记号中。

　　如果算法中包含嵌套的循环，则基本语句通常是最内层的循环体，如果算法中包含并列的循环，则将并列循环的时间复杂度相加。例如：

for (i=1; i<=n; i++)  
       x++;  
for (i=1; i<=n; i++)  
    　for (j=1; j<=n; j++)  
          x++;

　　第一个for循环的时间复杂度为Ο(n)，第二个for循环的时间复杂度为Ο(n²)，则整个算法的时间复杂度为Ο(n+n²)=Ο(n²)。

2.6、在计算算法时间复杂度时有以下几个简单的程序分析法则

(1).对于一些简单的输入输出语句或赋值语句,近似认为需要O(1)时间

(2).对于顺序结构,需要依次执行一系列语句所用的时间可采用大O下"求和法则"

求和法则:是指若算法的2个部分时间复杂度分别为 T1(n)=O(f(n))和 T2(n)=O(g(n)),则 T1(n)+T2(n)=O(max(f(n), g(n)))

特别地,若T1(m)=O(f(m)), T2(n)=O(g(n)),则 T1(m)+T2(n)=O(f(m) + g(n))

(3).对于选择结构,如if语句,它的主要时间耗费是在执行then字句或else字句所用的时间,需注意的是检验条件也需要O(1)时间

(4).对于循环结构,循环语句的运行时间主要体现在多次迭代中执行循环体以及检验循环条件的时间耗费,一般可用大O下"乘法法则"

乘法法则: 是指若算法的2个部分时间复杂度分别为 T1(n)=O(f(n))和 T2(n)=O(g(n)),则 T1*T2=O(f(n)*g(n))

(5).对于复杂的算法,可以将它分成几个容易估算的部分,然后利用求和法则和乘法法则技术整个算法的时间复杂度

另外还有以下2个运算法则:(1) 若g(n)=O(f(n)),则O(f(n))+ O(g(n))= O(f(n))；(2) O(Cf(n)) = O(f(n)),其中C是一个正常数

2.7、常见复杂度示例

(1)、O(1)

Temp=i; i=j; j=temp;                 

　　以上三条单个语句的频度均为1，该程序段的执行时间是一个与问题规模n无关的常数。算法的时间复杂度为常数阶，记作T(n)=O(1)。注意：如果算法的执行时间不随着问题规模n的增加而增长，即使算法中有上千条语句，其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。

(2)、O(n²)

a、 交换i和j的内容

sum=0；                 （一次）  
for(i=1;i<=n;i++)     （n+1次）  
   for(j=1;j<=n;j++) （n2次）  
    sum++；            （n2次）

解：因为Θ(2n²+n+1)=n²（Θ即：去低阶项，去掉常数项，去掉高阶项的常参得到），所以T(n)= =O(n²)；

b、

for (i=1;i<n;i++)  
 {   
     y=y+1;         ①     
     for (j=0;j<=(2*n);j++)      
        x++;         ②        
 }          

解： 语句1的频度是n-1
          语句2的频度是(n-1)*(2n+1)=2n²-n-1
          f(n)=2n²-n-1+(n-1)=2n²-2；

        又Θ(2n²-2)=n²
          该程序的时间复杂度T(n)=O(n²).  

　　一般情况下，对步进循环语句只需考虑循环体中语句的执行次数，忽略该语句中步长加1、终值判别、控制转移等成分，当有若干个循环语句时，算法的时间复杂度是由嵌套层数最多的循环语句中最内层语句的频度f(n)决定的。     

(3)、O(n)                                                              

a=0;  
  b=1;                      ①  
  for (i=1;i<=n;i++) ②  
  {    
     s=a+b;　　　　③  
     b=a;　　　　　④    
     a=s;　　　　　⑤  
  }  

解： 语句1的频度：2,        
           语句2的频度： n,        
          语句3的频度： n-1,        
          语句4的频度：n-1,    
          语句5的频度：n-1,                                  
          T(n)=2+n+3(n-1)=4n-1=O(n).
(4)、O(log₂n)

i=1;     ①  
hile (i<=n)  
  i=i*2; ②

解： 语句1的频度是1,  
          设语句2的频度是f(n),   则：2^f(n)<=n;f(n)<=log₂n    
          取最大值f(n)=log₂n,
          T(n)=O(log₂n )

(5)、O(n³) 

for(i=0;i<n;i++)  
   {    
      for(j=0;j<i;j++)    
      {  
         for(k=0;k<j;k++)  
            x=x+2;    
      }  
   }  

解：当i=m, j=k的时候,内层循环的次数为k当i=m时, j 可以取 0,1,...,m-1 , 所以这里最内循环共进行了0+1+...+m-1=(m-1)m/2次所以,i从0取到n, 则循环共进行了: 0+(1-1)*1/2+...+(n-1)n/2=n(n+1)(n-1)/6所以时间复杂度为O(n³).

2.8、 常用的算法的时间复杂度和空间复杂度

常用的排序算法的时间复杂度和空间复杂度

查找算法时间复杂度

 是

三、空间复杂度

　　当今硬件的存储量级比较大，一般不会为了稍微减少一点儿空间复杂度而大动干戈，更多的是去想怎么优化算法的时间复杂度。所以我们在日常写代码的时候就衍生出了用「空间换时间」的做法，并且成为常态。比如我们在求解斐波那契数列数列的时候我们可以直接用公式去递归求，用哪个求哪个，同样也可以先把很多结果都算出来保存起来，然后用到哪个直接调用，这就是典型的用空间换时间的做法 

1-07Python列表与字典操作的时间复杂度

list内置操作的时间复杂度

long long Fib(int N)
{
     if(N < 3)
    	return 1;
    
    return Fib(N-1) + Fib(N-2);
}

// 请计算一下Func1中++count语句总共执行了多少次？
void Func1(int N)
{
    int count = 0;
    for (int i = 0; i < N ; ++ i)
    {
        for (int j = 0; j < N ; ++ j)
        {
        	++count;
        }
    }
    for (int k = 0; k < 2 * N ; ++ k)
    {
   		 ++count;
    }
    int M = 10;
    while (M--)
    {
    	++count;
    }   
    printf("%d\n", count);
}

// 计算Func2的时间复杂度？
void Func2(int N)
{
    int count = 0;
    for (int k = 0; k < 2 * N ; ++ k)
    {
 	   ++count;
    }
    int M = 10;
    while (M--)
    {
   		++count;
    }
    printf("%d\n", count);
}

// 计算Func3的时间复杂度？
void Func3(int N, int M)
{
    int count = 0;
    for (int k = 0; k < M; ++ k)
    {
 	   ++count;
    }
    for (int k = 0; k < N ; ++ k)
    {
  		++count;
    }
    printf("%d\n", count);
}

// 计算Func4的时间复杂度？
void Func4(int N)
{
    int count = 0;
    for (int k = 0; k < 100; ++ k)
    {
    	++count;
    }
    printf("%d\n", count);
}

// 计算strchr的时间复杂度？
const char * strchr ( const char * str, int character );

// 计算BubbleSort的时间复杂度？
void BubbleSort(int* a, int n)
{
    assert(a);
    for (size_t end = n; end > 0; --end)
    {
        int exchange = 0;
        for (size_t i = 1; i < end; ++i)
        {
            if (a[i-1] > a[i])
            {
                Swap(&a[i-1], &a[i]);
                exchange = 1;
            }
        }
        if (exchange == 0)
        break;
    }
}

// 计算BinarySearch的时间复杂度？
int BinarySearch(int* a, int n, int x)
{
    assert(a);
    int begin = 0;
    int end = n-1;
    while (begin <= end)
    {
        int mid = begin + ((end-begin)>>1);//防溢出
        if (a[mid] < x)
        	begin = mid+1;
        else if (a[mid] > x)
        	end = mid-1;
        else
        	return mid;
    }
    return -1;
}

// 计算阶乘递归Fac的时间复杂度？
long long Fac(size_t N)
{
    if(0 == N)
    return 1;
    return Fac(N-1)*N;
}

// 计算斐波那契递归Fib的时间复杂度？
long long Fib(size_t N)
{
    if(N < 3)
    return 1;
    return Fib(N-1) + Fib(N-2);
}

// 计算BubbleSort的空间复杂度？
void BubbleSort(int* a, int n)
{
    assert(a);
    for (size_t end = n; end > 0; --end)  

    {
        int exchange = 0;
        for (size_t i = 1; i < end; ++i)
        {
            if (a[i-1] > a[i])
            {
                Swap(&a[i-1], &a[i]);
                exchange = 1;
            }
        }
        if (exchange == 0)
        break;
    }
}

// 计算Fibonacci的空间复杂度？
// 返回斐波那契数列的前n项
long long* Fibonacci(size_t n)
{
    if(n==0)
    	return NULL;
    long long * fibArray = (long long *)malloc((n+1) * sizeof(long long));
    fibArray[0] = 0;
    fibArray[1] = 1;
    for (int i = 2; i <= n ; ++i)
    {
    	fibArray[i] = fibArray[i - 1] + fibArray [i - 2];
    }
    return fibArray;
}

// 计算阶乘递归Fac的空间复杂度？
long long Fac(size_t N)
{
    if(N == 0)
    return 1;
    return Fac(N-1)*N;
}

// 计算斐波那契递归Fib的空间复杂度？
long long Fib(size_t N)
{
    if(N < 3)
    return 1;
    return Fib(N-1) + Fib(N-2);
}

long long Fib(int N)
{
	if (N < 3)
		return 1;
	return Fib(N - 1) + Fib(N - 2);
}

void Func1(int N)
{
	int count = 0;
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < N; ++j)
		{
			++count;
		}
	}
	for (int k = 0; k < 2 * N; ++k)
	{
		++count;
	}
	int M = 10;
	while (M--)
	{
		++count;
	}
	printf("%d\n", count);
}

void Func2(int N)
{
	int count = 0;
	for (int k = 0; k < 2 * N; ++k)
	{
		++count;
	}
	int M = 10;
	while (M--)
	{
		++count;
	}
	printf("%d\n", count);
}

void Func3(int N, int M)
{
	int count = 0;
	for (int k = 0; k < M; ++k)
	{
		++count;
	}
	for (int k = 0; k < N; ++k)
	{
		++count;
	}
	printf("%d\n", count);
}

void Func4(int N)
{
	int count = 0;
	for (int k = 0; k < 100; ++k)
	{
		++count;
	}
	printf("%d\n", count);
}

const char* strchr(const char* str, int character)
{
	while (*str != character)
	{
		str++;
	}
	return str;
}

void BubbleSort(int* a, int n)
{
	assert(a);
	for (size_t end = n; end > 0; --end)
	{
		int exchange = 0;
		for (size_t i = 1; i < end; ++i)
		{
			if (a[i - 1] > a[i])
			{
				Swap(&a[i - 1], &a[i]);
				exchange = 1;
			}
		}
		if (exchange == 0)
			break;
	}
}

int BinarySearch(int* a, int n, int x)
{
	assert(a);
	int begin = 0;
	int end = n - 1;
	// [begin, end]：begin和end是左闭右闭区间，因此有=号
	while (begin <= end)
	{
		int mid = begin + ((end - begin) >> 1);
		if (a[mid] < x)
			begin = mid + 1;
		else if (a[mid] > x)
			end = mid - 1;
		else
			return mid;
	}
	return -1;
}

long long Fac(size_t N)
{
	if (0 == N)
		return 1;
	return Fac(N - 1) * N;
}

long long Fib(size_t N)
{
	if (N < 3)
		return 1;
	return Fib(N - 1) + Fib(N - 2);
}

void BubbleSort(int* a, int n)
{
	assert(a);
	for (size_t end = n; end > 0; --end)
	{
		int exchange = 0;
		for (size_t i = 1; i < end; ++i)
		{
			if (a[i - 1] > a[i])
			{
				Swap(&a[i - 1], &a[i]);
				exchange = 1;
			}
		}
		if (exchange == 0)
			break;
	}
}

// 返回斐波那契数列的前n项
long long* Fibonacci(size_t n)
{
	if (n == 0)
		return NULL;
	long long* fibArray = (long long*)malloc((n + 1) * sizeof(long long));
	fibArray[0] = 0;
	fibArray[1] = 1;
	for (int i = 2; i <= n; ++i)
	{
		fibArray[i] = fibArray[i - 1] + fibArray[i - 2];
	}
	return fibArray;
}

long long Fac(size_t N)
{
	if (N == 0)
		return 1;
	return Fac(N - 1) * N;
}

long long Fib(size_t N)
{
	if (N < 3)
		return 1;
	return Fib(N - 1) + Fib(N - 2);
}

void reverse(int* nums, int left, int right)
{
    while (left < right)
    {
        int tmp = nums[left];
        nums[left] = nums[right];
        nums[right] = tmp;
        ++left;
        --right;
    }
}
void rotate(int* nums, int numsSize, int k){
    k %= numsSize;
    reverse(nums, 0, numsSize - 1 - k);
    reverse(nums, numsSize - k, numsSize - 1);
    reverse(nums, 0, numsSize - 1);
}