如何找到这段特定代码的时间复杂度?

问题描述 投票:0回答:1

我已经审阅了导师提供的很多材料,并广泛搜索了谷歌并观看了视频,虽然我对如何确定基本时间复杂度有一些了解,但我很难真正验证我的答案是否正确。对于上下文,我试图确定我将在下面提供的方法的最坏情况时间复杂度。

我已经知道什么了

举一个简单的 for 循环,如下所示:

for (int k = 0; k < n; k++)
{
    Console.WriteLine("Hello world");
}
  • int k=0;这只会执行一次。 时间实际上是计算到 k=0 而不是声明的。

  • k< N; This will be executed N+1 times k++ This will be executed N times So the number of operations required by this loop are {1+(N+1)+N} = 2N+2. (But this still may be wrong, as I am not confident about my understanding.)

好的,所以这些小的基本计算我想我知道,但在大多数情况下我看到的时间复杂度为 O(N), O(n^2), O(log n), O(n!)

所以我的主要问题是如何确定下面所示代码的最坏情况时间复杂度

public void Add(IMember member)
{
    // To be implemented by students
    Member amember = new Member(member.FirstName, member.LastName, member.ContactNumber, member.Pin);
    if (IsEmpty())
    {
        members[0] = amember;
        count++;
        return;
    }


    for (int j = 0; j < count; j++)
    {
        if (members[j].FirstName == amember.FirstName && members[j].LastName == amember.LastName)
        {
            return; // this member is a duplicate so we simply ignore it and dont add it to the array of members 
        }
    }

    int i;
    for (i = count - 1; i >= 0; i--)
    {
        // use the compare method to compare members 
        if (members[i].CompareTo(amember) > 0)
        {

            // if the current member should come after the new member move it up to make space
            members[i + 1] = members[i];
        }

        else
        {
            // found the position break from the loop 
            break;
        }
    }

    // insert the new member 
    members[i + 1] = amember;
    count++;

   
}

这是 CompareTO 方法代码,在大多数情况下会影响很多输出:

public int CompareTo(IMember member)
{
    // concatenate the members first and lastname into a full name
    string fullnamethis = this.firstName + " " + this.lastName;
    string fullnameother = member.FirstName + " " + member.LastName;

    // considering the fullname ensures that in cases where someone has the same first name but a different last name they are still added to the members array
    // instead of being considered duplicates
    return fullnamethis.CompareTo(fullnameother);
}

背景

对于上下文来说,这是一种算法,用于将新成员添加到成员集合对象中,在本例中是一个数组。此方法的目的是将新成员添加到集合中,并保持集合按名字和姓氏的字母顺序排序。现在,虽然这是成功的,但我们因为开发了一种低效的算法而失去了分数,该算法在最坏的情况下将被归类为以 O(n^2) 时间复杂度运行的算法。所以我的目标是如果需要的话修改这个方法,将最坏情况的时间复杂度提高到 O(n) 甚至 O(n log n)(如果可能的话)。

但我仍然面临的主要问题是确定它是否确实需要修改,因为我相信我的时间复杂度可能为 O(n^2),而它没有明确使用嵌套 forloop。使用 CompareTo 操作意味着每个成员都会被访问两次(据我所知,我的想法可能是错误的),我相信这将使该方法的最坏情况时间复杂度为 O(n^2)。

如果有人能够提供一些关于我的想法是否正确的见解,如果我是正确的,可能会提供一些关于如何重构代码以达到所需时间复杂度的提示。

c# algorithm time time-complexity
1个回答
0
投票

首先,我认为这里的

n
指的是会员数量。

对于这个

Add
方法,它的时间复杂度是
O(n)
,因为在最坏的情况下,当你添加一个新成员时,你需要将它与每个已经添加的成员进行比较。随着更多成员的加入,比较的次数也会成比例增加。

但是如果他们考虑添加总共

n
成员的时间复杂度,那么就是
O(n^2)

© www.soinside.com 2019 - 2024. All rights reserved.