Как я могу найти временную сложность этого конкретного кода? ⇐ C#

[Anonymous]

Я просмотрел множество материалов, предоставленных преподавателями, много искал в Google и смотрел видео, и, хотя у меня есть некоторое представление о том, как определять основные временные сложности, мне сложно действительно проверить, правильный ли мой ответ. Для контекста я пытаюсь определить наихудшую временную сложность метода, который я приведу ниже.
Что я уже знаю
Скажем, для простого цикла for, подобного показанному ниже:

Код: Выделить всё

for (int k = 0; k < n; k++)
{
Console.WriteLine("Hello world");
}

• int k=0; Это будет выполнено только один раз.
  
  Фактическое время рассчитывается как k=0, а не как объявление.
• к < Н; Это будет выполнено N+1 раз
  
  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).
Если кто-то может дать некоторое представление о том, правильно ли я думаю или нет, и если я прав, возможно, дайте несколько советов о том, как я могу провести рефакторинг кода. для достижения желаемой временной сложности.

Подробнее здесь: https://stackoverflow.com/questions/783 ... cular-code