Kotlin 单个等号“=”对象赋值时间复杂度

Question

Kotlin（或Java）中使用等号赋值对象的时间复杂度是多少？

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

更具体地说，如果我有自己的对象 ListNode

 * 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

Answer 1

作业

var l1Copy = l1

不会生成包含与 l1 相同属性的新 ListNode 对象。它只是创建一个名为 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 的范围内。

Answer 2

If 方法仅包含常数时间赋值语句、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];

Kotlin 单个等号“=”对象赋值时间复杂度

Kotlin single equal sign "=" object assignment time complexity

java

big-o

kotlin