1.1 Большой O

Это метод анализа использования ресурсов алгоритма. Ресурсы указывают время работы, память, хранилище, сеть и т. Д., Но ресурсы, относящиеся к интервью, указывают время работы. Время выполнения зависит от среды выполнения. Поэтому вместо измерения времени выполнения подсчитывается счет выполнения операции. Количество раз, когда операция выполняется, выражается функцией, относящейся к размеру входных данных. Когда количество данных n равно ∞, временная сложность выражается скоростью роста, с которой увеличивается время выполнения. Это не единственный и не лучший метод. Однако это относительно просто и не зависит от среды выполнения алгоритма. Поэтому он наиболее широко используется.

  • Один из способов указания количества выполнений операций, включенных в алгоритм
  • Показывать только порядок наивысшего порядка
  • Поэтому достаточно учитывать, сколько раз выполняются наиболее часто выполняемые операции или инструкции.

§ O (1) - Постоянная сложность времени

Независимо от n требуется постоянное время. В этом случае сложность времени O (1).

func sample (_data:[int],_ n:int) -> int{
  var k = n/2
  return data[k]
}

§ O (logN) -Сложность логарифмического времени

В logN символ «log» - это подчеркнутая форма, обычно log2 N. Алгоритм с временной сложностью logN решит проблему, постепенно уменьшая количество данных вдвое, когда данные уже предоставлены. Например, если первое заданное N равно 16, данные будут уменьшаться до 8, 4, 2 и 1 по очереди каждый раз, когда вы их обрабатываете. Это число 4 означает log2N = log2 16. Нередко возникают проблемы с алгоритмами O (logN), но они иногда возникают в процессе разработки некоторых алгоритмов.

§ O (N) -Сложность линейного времени

Когда вводится N данных, временная сложность занимает O (N), даже если эти фрагменты данных вводятся только один раз. И наоборот, если временная сложность равна O (N), то только чтение данных решит проблему. Алгоритм, решающий эту проблему, называется «алгоритмом сканирования», а время выполнения - «линейным». В большинстве случаев алгоритм O (N) будет самым идеальным алгоритмом, к которому мы стремимся. Это связано с тем, что нет алгоритмов быстрее, чем O (N), за исключением случаев, когда предполагается, что нет времени на чтение данных, например O (1) или O (logN).

Наиболее часто выполняемый оператор в этом коде - оператор «for», и счетчик выполнения всегда равен n раз. Если количество выполнений наиболее часто выполняемых операторов равно n раз, сумма времени выполнения всего кода линейно пропорциональна n, а сумма времени выполнения всех операций также линейно пропорциональна N.

func sum (_data:[int],_ n:int) -> int {
  var sum = 0
  for i in 0...n-1{
    sum = sum + data[i]
  }
  return sum
}

§ O (NlogN) - Сложность за долгое линейное время

Это время выполнения происходит от программы, которая запускается O (N) раз на каждом шаге, разбивая проблему на более мелкие. Вы увидите многие из этих временных сложностей среди многих эффективных алгоритмов. Поскольку значение «logN» намного меньше, чем N, O (NlogN) не намного медленнее, чем O (N).

§ O (N²) -Сложность квадратичного времени

O (N²) - это наиболее часто встречающаяся временная сложность. N * (N-1) = N²-N случаев генерируется, когда N элементов объединены друг с другом, поэтому часто встречается алгоритм O (N²). Наиболее типичный пример - использование оператора double for для сравнения всех чисел и всех чисел и сортировки по размеру.

Наиболее часто исполняемый оператор в алгоритме - это двойной оператор For, и в худшем случае количество выполнений равно n (n-1) / 2.
В худшем случае временная сложность составляет O (n² ).

func is_distinct(_data:[int],_ n:int) -> bool{
  var sum = 0
  for i in 0...n-1{
    for j in i+1...n{
      if data[i] == data[j]{
        return false
      } 
    }
  }
  return sum
}

§ O (N³) -Сложность кубического времени

Он показывает «кубическое» время выполнения как временную сложность при использовании оператора тройного цикла.

§ O (2 ^ N) -Экспоненциальная временная сложность

Если log2 X = N, то появится 2 ^ N = X. O (2 ^ N) противоположно O (logN). O (2N) удваивает регистр каждый раз, когда N увеличивается, если O (logN) нужно уменьшить вдвое. Самый распространенный пример - монета. Количество N монет с лицевой и оборотной сторонами, которые могут быть выстроены в линию, равно 2 ^ N.

Когда мы решаем проблему и разрабатываем алгоритмы O (2 ^ N), мы должны учитывать все возможные ситуации, выбирая, следует ли выбирать каждые данные, когда дано N данных.

Если N экспоненциально, например O (2 ^ N) или O (N²), это трудоемкая и неэффективная временная сложность. O (2 ^ N) обычно не отвечает в отведенное время, если N превышает 20 ~ 30. Когда число показателей увеличивается на единицу, насколько велико общее число, можно легко определить, запрограммировав программу со сложностью времени O (2 ^ N) или O (N²).

§ O (N ^ N) - Факторная сложность времени

O (N ^ N) - наихудшая временная сложность, с которой мы можем столкнуться. N ^ N и N! Принадлежит к временной сложности O (N ^ N). Даже если N чуть больше 10, ответ не доступен вовремя. Эта временная сложность возникает, когда вам нужно найти все возможные комбинации N данных.