Расчет ожидаемого времени работы функции

Question

У меня возник вопрос о вычислении ожидаемого времени работы данной функции. Я прекрасно понимаю, как рассчитать фрагменты кода с циклами в них (для/while/if и т. Д.), Но функции без них кажутся мне немного странными. Например, предположим, что мы имеем следующий фрагмент кода:

public void Add(T item) 
{ 
    var newArr = new T[this.arr.Length + 1]; 
    Array.Copy(this.arr, newArr, this.arr.Length); 
    newArr[newArr.Length - 1] = item; 
    this.arr = newArr; 
} 

Если моя логика работает правильно, функция Add имеет сложность O (1), потому что в лучшем/худшем/средний случае это будет просто читать каждую строку кода один раз, правильно?

Answer 1

Вы всегда должны учитывать временную сложность вызовов функций. Я не знаю, как реализовано Array.Copy, но я собираюсь догадаться, что это O(N), что делает всю функцию AddO(N). Разумеется, ваша интуиция правильная, но отдыхает. Фактически это O(1).

Answer 2

Если у вас есть несколько суба-операция с О (п) + O (журнал (п)) и т.д., и дорогостоящий шагом является стоимостью всей операции - по умолчанию большого O относится к худшему случаю , Здесь, как и скопировать массив, это О (п) операции

Answer 3

Сложность вычисляется Вслед за этим 2 правила:

-Calling метод (сложность + 1)

-Encountering следующие ключевые слова: если, в то время как, повторяю, для, & &, ||, поймать, случай и т.д ... (сложности + 1)

в вашем случае, дарованной вам пытаются скопировать массив, а не какое-либо значение, алгоритм завершит N операции копирования, дающие вам O (N).