【数据结构】时间复杂度的例题

🎁个人主页：我们的五年

🔍系列专栏：数据结构

🌷追光的人，终会万丈光芒

目录

 🌷例题1：

🌷例题2：

🌷例题3：

🌷例题4：

🌷例题5：

模拟实现可以看成这样：

🌷例题6：

🌷例题7：

🌷例题8：

🌷例题9：

---

 前言：
这篇文章是关于时间复杂度的一些例题，关于时间复杂度和空间复杂度和算法的计算效率的基本知识点我放在这篇文章。

数据结构：时间复杂度

最后喜欢的铁子可以点点关注，互关私信，感谢大家的支持，祝大家天天开心！

 🌷例题1：

// 请计算一下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);
}

 F(N)=N^2+2*N+10

第一个循环：N^2

第二个循环：2*N

while循环：10

O(N^2)只看最高次项，这就是N^2.

时间复杂度：O(N^2)

🌷例题2：

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);
}

 F(N)=2*N+10

时间复杂度：O(N)

🌷例题3：
 

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);
}

 F(N)=M+N

时间复杂度：O(M+N)

🌷例题4：

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

F(N)=100

循环次数为常数，所以

 时间复杂度：O(1)

🌷例题5：

// 计算strchr的时间复杂度？

const char * strchr ( const char * str, int character );

strchr函数是在str字符串中寻找字符character，如果找到了就返回该字符的地址，否则返回NULL

模拟实现可以看成这样：

const char * strchr ( const char * str, int character )

{

        while(*str!='\0')

        {

                if(*str==character)

                        return str;

                else

                        str++;

        }

        return NULL;
}

最好的情况基本操作执行了1次，最坏的情况基本操作执行了N次，时间复杂度是考虑最坏的情况，所以

时间复杂度：O(N)

🌷例题6：

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次，就是已经是拍好的序列，此时exchange=0，直接退出循环

最好的情况基本操作执行了（N-1）！=N*(N-1)/2

而时间复杂度是看最坏情况，而且是估算，所以-1和处以2可以省略。

时间复杂度：O(N^2)

🌷例题7：

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;
}

 最好情况时一次，最坏情况时log N次

ps：logN在算法分析中表示是底数为2，对数为N。有些地方会写成lgN。

（建议通过折纸查找的方式讲解logN是怎么计算出来的）

时间复杂度：OogN)

🌷例题8：

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

 循环了n次

时间复杂度：O(N)

🌷例题9：

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

基本操作次数为2^N次，

时间复杂度：O(2^N)

总结：

该文章提供了时间复杂度的一些基本例题，后面还有一篇文章是在真正的题目中进行应用时间复杂度去题，时间复杂度可以去判断一个算法的优劣，从而得到最优解法。