C语言数据结构-如何判断时间复杂度和空间复杂度_判断时间复杂度并说明原因

作者：运维做开发 | 2024-07-04 16:08:57

踩

判断时间复杂度并说明原因

如何才能评价一个算法效率，我们往往通过时间复杂度和空间复杂度来描述。

一、时间复杂度

由于在不同的硬件设备，不同的软件系统的环境下，我们很难准确地描述一个程序具体运行的时间，所以我们提出了一个时间复杂度的概念来描述一个程序的时间效率。

一个语句的频度指这个语句在算法中被重复执行的次数。算法中所有语句的频度值和记为T(n)

在下面的语句中，我们可以看到这段代码中++count所执行的次数为 $N^{2}$ +2*N+10次

N = 10 F(N) = 130

N = 100 F(N) = 10210

N = 1000 F(N) = 1002010

在N逐渐变大时，影响我们执行次数的数据主要是 $N^{2}$ ，所以我们可以认为这段代码的时间复杂度为T(n)=O( $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);
}

在计算时间复杂度的时候，我们不需要精确地计算算出这个程序中语句执行的精确次数，只需要估算出大概的执行次数即可。这里我们可以采用大O渐进法来描述时间复杂度

大O符号（Big O notation）：是用于描述函数渐进行为的数学符号。

推导大O阶方法：

1、用常数1取代运行时间中的所有加法常数。

2、在修改后的运行次数函数中，只保留最高阶项。

3、如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶

算法的时间复杂度不仅仅取决于算法本身，还可能取决于所输入的数据。

比如在下面的代码中我们在一个长度为100的数组a中查找数据值为10的元素，但是由于我们的a数组中所含的元素具有极大的随机性，所以我们所要查找的数据10可能是在第一个，也可能是在最后一个。


    for (int i=0;i<N;i++)
    {
        printf("%d",a[i]);
        if(a[i]==10)
        {
            printf("%d",i);
 
            break;
        }
    }