我怎样才能找到这个特定代码的时间复杂度？

Question

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

我已经知道什么了

举一个简单的 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++ 这会执行N次
  所以这个循环所需的运算次数为{1+(N+1)+N} = 2N+2。 （但这仍然可能是错误的，因为我对自己的理解没有信心。）

好的，所以这些小的基本计算我想我知道，但在大多数情况下我看到的时间复杂度为 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 don't 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)，而它没有明确使用嵌套

for

循环。使用

CompareTo

操作意味着每个成员都会被访问两次（据我所知，我的想法可能是错误的），我相信这将使该方法的最坏情况时间复杂度为 O(n^2) .

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

Answer 1

首先，我认为这里的

n

指的是会员数量。

对于这个

Add

方法，它的时间复杂度是

O(n)

，因为在最坏的情况下，当你添加一个新成员时，你需要将它与每个已经添加的成员进行比较。随着更多成员的加入，比较的次数也会成比例增加。

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

n

成员的时间复杂度，那么就是

O(n^2)