swift - 如何计算循环的时间复杂度 - Swift

Question

我给出了两个具有不同时间复杂度的循环示例。一个是二次的，另一个是对数的。任何人都可以帮助我为什么时间复杂度不同，因为两个代码迭代相同次数但操作不同？

时间复杂度的因素是什么？没有次数或操作？

//Quadratic O(n^2)
var c = 0
for i in 1...100{
    c = Int(pow(Double(i), 2))
}

//Logarithamic O(log n)
var d = 0
for i in 1...100{
    d = Int(log(Double(i)))
}

Answer 1

这两个循环具有相同的时间复杂度 - O(1) 常数时间，因为它们总是会运行 100 次。与他们无关

如您所知，时间复杂度衡量算法运行所需的时间如何随变量变化而变化。例如，这个循环的时间复杂度为 O(n):

for i in 0..<n {
    print(i)
}

随着 n 的增加，运行该循环所需的时间线性增加，因此 O(n)。

这个循环是 O(n^2):

for i in 0..<(n*n) {
    print(i)
}

这个循环是 O(log(n)):

for i in 0..<Int(log(n)) {
    print(i)
}

(显然还有其他方法可以实现 O(n^2) 和 O(log(n)) 循环)

我认为给定的循环只是为了说明不同的时间复杂度，方法是绘制所需时间随 n 增加而增加的“图表”。从屏幕截图中可以看出，O(log(n)) 循环绘制了一个 log(n) 图。