Котлин один знак равенства "=" сложность задания объекта по времени

#java #kotlin #big-o

Вопрос:

Какова временная сложность назначения объектов с использованием знака равенства в Kotlin (или Java)?

 fun moveZeroes(nums: IntArray): Unit {
    var numsCopy = nums
}

Более конкретно, если у меня есть свой собственный список объектов

  * Example:
 * var li = ListNode(5)
 * var v = li.`val`
 * Definition for singly-linked list.
 * class ListNode(var `val`: Int) {
 *     var next: ListNode? = null
 * }
 */

Каково будет время копирования ниже?

 fun mergeTwoLists(l1: ListNode?, l2: ListNode?): ListNode? {
    var l1Copy = l1
}

Я часто выполняю это задание, так как ListNode проходит как val, и я не могу этого сделать

 l1 = l1?.next

Ответ №1:

Задание

 var l1Copy = l1

не создает новый ListNode объект, содержащий те же свойства, l1 что и . Он просто создает новую переменную с именем l1Copy и указывает ее в ту же ячейку памяти l1 , что и, так что это операция O(1).

В следующем коде

 fun f(n: ListNode) {
    var n1 = n
}

val node = ListNode(1)
val var1 = node
f(node)

есть только один объект ListNode(1) и три переменные, указывающие на него: node и var1 в глобальной области, и n и n1 в f области.

1. Этот ответ верен. Список-это объект, и объекты всегда передаются по ссылке, даже для назначений. Для копирования OP должен использовать соответствующую copy() функцию. Это следует добавить к ответу.

2. Отличный ответ, спасибо. Поэтому в моем первом примере я передавал узел списка в функцию в качестве параметра. Все параметры передаются как val в котлине. Если я сделаю var l1Copy = l1 это, как l1Copy станет изменяемым, если l1 он был неизменяемым и l1Copy является просто указателем на ту же ячейку памяти? Изменение l1Copy , кажется, не меняется l1

Ответ №2:

Если метод содержит только операторы присваивания с постоянным временем, операторы if, условные выражения и тому подобное, скорее всего, это операция или метод с постоянным временем. Если он содержит цикл, есть вероятность, что он не является постоянным по времени.

Но вы должны быть осторожны, как показывает следующий пример. Рассмотрим массив b и следующие операторы:

 int sum= 0;
for (int k= 0; k < Math.min(50, b.length); k= k 1)
    sum= sum   b[k];

Поскольку цикл повторяется не более 50 раз, и поскольку каждое выражение или назначение в нем является операцией с постоянным временем,
сам код является постоянным временем. Например, он содержит максимум 50 добавлений элементов массива, независимо от того, насколько велик
массив. Но следующий цикл с инициализацией не является постоянным временем, а занимает время, пропорциональное размеру b.

 int sum= 0;
for (int k= 0; k < b.length; k= k 1)
   sum= sum   b[k];