python - 我的牛顿法和二分法的时间复杂度是多少?
问题描述
我对 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。
有人可以澄清并告诉我我是对还是错?提前致谢!
解决方案
TLDR:这取决于功能,所以,也许这个问题不适用。
解释和假设:这两种算法都在寻找零函数。我假设您将 n 定义为1/e
,其中e
是所需的精度。
第一个算法,二分法,是 O(log mn),其中 m 是初始间隔的宽度。证明:我们正在通过 mn 个子间隔进行二进制搜索。
然而,第二个的复杂性取决于功能。对于线性函数,它将是O(1)
。对于某些功能,它会永远收敛(例如:)y = sin(x) + 2 - x / 1000000
。因此,答案取决于函数,不仅取决于函数的类别(线性、二次等),而且在某些情况下,还取决于特定的系数和 的选择x_0
。
精确的收敛特性由高阶导数定义。在这种特殊情况下,一阶导数始终为负,因此它会收敛;但是,如果没有2x
术语,它将有一个拐点,该拐点将x_n
陷入无穷大。
Protip:它更具可读性
while True:
...
if condition:
break
UPD:假设n
是x_0
从函数零的距离,在这种特殊情况下:
在更新步骤中,delta ( f/f_d
) 与 x 成正比。我们正在寻找总和为 n 的一些增量。等差数列 (n) 的总和为 O(N^2),其中 N 是步数。所以步数是 O(sqrt(n))。
重要提示:如上所述,这通常不是牛顿法的复杂性。这仅适用于这个特定的功能,甚至不会推广到同一类的其他功能。这个问题本身并没有太多的实际意义(例如,我们可以在封闭的形式中找到零)并且它不是一个特别令人印象深刻的分析。请小心使用。
推荐阅读
- ios - iOS swift:在旋转动画中间更改imageview图像
- android - 访问 Fragment 中的资产
- sql - 如何在年和年-1 的列中编写查询让值?
- selenium - 测试按钮同时在浏览器的不同选项卡中单击
- android - Long amount of time elapses before onServiceConnected() is called
- c++ - 示例程序崩溃
- azure - 如何在 Microsoft Chatbot 服务中设置问候语
- html - html宽度导致滚动条
- python-3.x - 正方体错误
- java - 什么原因导致 EXCEPTION_ACCESS_VIOLATION 以及如何解决?