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

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）。因此，答案取决于函数，不仅取决于函数的类别（线性，二次函数等），而且在某些情况下还取决于特定系数和x_0的选择。

确切的收敛特性由高阶导数定义。在这种特殊情况下，一阶导数始终为负，因此将收敛。但是，如果没有2x项，它将有一个拐点，这将使x_n进入无穷大。