我的牛顿法和二分法算法的时间复杂度是多少？

Question

我是 Big O 的新手，我一直在努力评估我的两种算法的时间复杂度，我应该为学校项目比较它们。

二分法：

import time


tid_0 = time.perf_counter_ns()

x_0 = -20000                       #Interval
x_1 = 20000

fortsæt = True
while fortsæt:
    f_x0 = x_0**3+2*x_0+4        #f = x**3+2x
    f_x1 = x_1**3+2*x_1+4         #Finder y værdier

    x_m = (x_0+x_1)/2           #Midtpunkt
    f_xm = x_m**3+2*x_m+4        #Midtpunkt y-værdi

    if f_x0 * f_x1 > 0:
        print("ERROR: Interval ugyldigt")
        exit()

    print(x_0, x_m, x_1)

    if f_x1 * f_xm < 0:         #Hvis = negativ tal
        x_0 = x_m
    elif f_x0 * f_xm < 0:
        x_1 = x_m

    if x_1-x_0 < 0.0009:        #Stopper While-loopet
        fortsæt = False


total = time.perf_counter_ns() - tid_0


print("total tid: " + str(total) + "ns")

牛顿法：

import time

tid_0 = time.perf_counter_ns() #Påbegynder tidtagning af programmet

x_0 = 20000  #Definere et startværdi x_0

fortsæt = True

while fortsæt:
    f = x_0 ** 3 + 2 * x_0 + 4  #Funktion f(x)
    f_d = 3 * x_0 ** 2 + 2    #Differentieret funktion f'(x)
    x_n = x_0-f/f_d         #Find x_0 - f(x_0) / (f'(x_0 )) = x_1
    print(x_n)

    if x_0 - x_n  < 0.0009:  #Stopper While-loopet, hvis forskellen mellem de to nulpunkter er 0,009
        fortsæt = False

    x_0 = x_n


total = time.perf_counter_ns() - tid_0

print("total tid: " + str(total) + "ns") #Printer den endelige køretid

根据我的最佳理解，我想我的牛顿法算法在最坏的情况下是 O(n)，在最好的情况下是 O(1)。不过，我不太确定。

另外，这里重要的变量是x_0。

有人可以澄清一下并告诉我我是对还是错吗？提前致谢！

Answer 1

TLDR: 这取决于功能，所以，也许这个问题不适用。

解释和假设：这两种算法都在寻找函数零。我假设您将 n 定义为 1/e，其中 e 是所需的精度。

第一个算法，二分法，是O(log mn)，其中m是初始区间的宽度。证明：我们正在通过 mn 个子区间进行二进制搜索。

然而，第二个的复杂性取决于功能。对于线性函数，它将是 O(1)。对于某些函数，它将永远收敛（例如：y = sin(x) + 2 - x / 1000000）。因此，答案取决于函数，不仅取决于函数的 class（线性、二次等），而且在某些情况下，还取决于特定系数和 x_0.[=21= 的选择]

精确的收敛特性由高阶导数定义。在这种特殊情况下，一阶导数总是负的，所以它会收敛；但是，如果没有 2x 项，它将有一个拐点，这将使 x_n 变成无穷大。

提示：

更易读

while True:
    ...
    if condition:
        break

UPD： 假设 n 是 x_0 与函数零的距离，在这种特殊情况下：

在更新步骤中，delta (f/f_d) 与 x 成正比。我们正在寻找总和为 n 的增量。等差级数之和 (n) 为 O(N^2)，其中 N 为步数。所以步数是 O(sqrt(n)).

重要提示： 如上所述，这不是一般牛顿法的复杂性。这仅适用于此特定功能，甚至不会推广到同一 class 的其他功能。这个问题本身没有太多实际意义（例如，我们可以在封闭形式中找到零）并且它不是一个特别令人印象深刻的分析。请小心使用。

我的牛顿法和二分法算法的时间复杂度是多少？

What is the time complexity of my Newton Method and Bisection algorithm?

python

algorithm

big-o

bisection