悟的复杂度分析

2024-01-09 22:37:44

复杂度分析:

? ? ? ? ? ? ? ? 时间复杂度(算法中的基本操作的执行次数);

? ? ? ? ? ? ? ? 空间复杂度。

时间复杂度:

实际上我们计算时间复杂度时,我们其实并不需要计算准确的执行次数,只需要大概的执行次数,因此我们在这里使用大O的渐进表示法。常见的时间复杂度O(1), O(N2), O(N),? ? ? ? ?O(logN)。

大O符号:

是用于描述函数渐进行为的数学符号。

推导大O阶方法:

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

例:

计算下面代码的时间复杂度

void f(int N)
{
    int count = 0;
    for(int k = 0; k < 100; ++k)
    {
         ++count;
    }
}

答案:O(1)

注:确定的常数次,都是O(1)。

2.在修改后的运行次数函数中,只保留最高阶项;

例:

计算下面代码的时间复杂度

void f(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", count);
}

答案:O(N2)

注:准确的执行次数:N2 + 2 * N + 10

? ? ?随着N的增大,这个表达式中N2对结果的影响最大

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

例:

计算下面代码的时间复杂度

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

答案:O(N)

特殊情况:

例一:

计算下面代码的时间复杂度

void f(int N, int M)
{
    int count = 0;
    for (int k = 0; k < N; k++)
    {
        ++count;
    }
    for (int k = 0; k < M; k++)
    {
        ++count;
    }
}

答案:O(M + N)

注:假如给了条件:M远大于N,答案是O(M);M和N差不多大,O(M)或O(N)。

例二:

计算下面代码的时间复杂度

const char* s(const char* str, char cha)
{
    while (*str != '\0')
    {
        if (*str == cha)
        {
            return str;
        }
        ++str;
    }
    return NULL;
}

假设字符串长度是N。

答案:O(N)

注:有些算法的时间复杂度存在最好,平均,最坏情况:

? ? ? ? 最坏:O(N)

? ? ? ? 平均:O(N/2)

? ? ? ? 最好:O(1)

在实际中一般情况关注的是算法的最坏运行情况。

例三:

计算下面代码的时间复杂度

void B(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)
        {
            break;
        }
    }
}

答案:O(N2)

注:第一趟冒泡:N

? ? ? ?第二趟冒泡:N - 1

? ? ? ?........?

? ? ? 第N趟:1

以上是个等差数列,所以准确的次数是(N+1)*N/2

时间复杂度为O(N2)

例四:

计算下面代码的时间复杂度

int B(int* a, int n, int x)
{
    assert(a);
    int begin = 0;
    int end = n;
    while (begin < end)
    {
        int mid = begin + ((end - begin) >> 1);
        if (a[mid] < x)
        {
            begin = mid + 1;
        }
        else if (a[mid] > x)
        {
            end = mid;
        }
        else
        {
            return mid;
        }
    }
    return - 1;
}

答案:O(logN)

注:假设找了X次

2的X的平方 = N

X=logN

因为有很多地方不好写底数,所以一般省略简写成logN。?

例五:

计算下面代码的时间复杂度

long long f(size_t N)
{
    return N < 2 ? N : f(N - 1) * N;
}

答案:O(N2)

注:递归调用了N次,每次递归运算--》O(1)

整体就是O(N)。

文章来源:https://blog.csdn.net/2301_80634989/article/details/135489461
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。