- iOS/Objective-C 元类和类别
- objective-c - -1001 错误,当 NSURLSession 通过 httpproxy 和/etc/hosts
- java - 使用网络类获取 url 地址
- ios - 推送通知中不播放声音
我发现这个算法计算 https://www.geeksforgeeks.org/median-of-two-sorted-arrays/ 上 2 个排序列表的中位数.它说,它是 O(log(n))。但事实真的如此吗?
我感到困惑的是:这些行将数组拆分为 2 个子数组(使用 Python 的切片)并递归求解:
if n % 2 == 0:
return getMedian(arr1[:int(n / 2) + 1],
arr2[int(n / 2) - 1:], int(n / 2) + 1)
else:
return getMedian(arr1[:int(n / 2) + 1],
arr2[int(n / 2):], int(n / 2) + 1)
但拆分数组对我来说看起来像 O(n)。所以在我看来,整个算法一定是O(n * log n)...
在这里,您可以看到我正在谈论的算法的完整代码:
# using divide and conquer we divide
# the 2 arrays accordingly recursively
# till we get two elements in each
# array, hence then we calculate median
#condition len(arr1)=len(arr2)=n
def getMedian(arr1, arr2, n):
# there is no element in any array
if n == 0:
return -1
# 1 element in each => median of
# sorted arr made of two arrays will
elif n == 1:
# be sum of both elements by 2
return (arr1[0]+arr2[1])/2
# Eg. [1,4] , [6,10] => [1, 4, 6, 10]
# median = (6+4)/2
elif n == 2:
# which implies median = (max(arr1[0],
# arr2[0])+min(arr1[1],arr2[1]))/2
return (max(arr1[0], arr2[0]) +
min(arr1[1], arr2[1])) / 2
else:
#calculating medians
m1 = median(arr1, n)
m2 = median(arr2, n)
# then the elements at median
# position must be between the
# greater median and the first
# element of respective array and
# between the other median and
# the last element in its respective array.
if m1 > m2:
if n % 2 == 0:
return getMedian(arr1[:int(n / 2) + 1],
arr2[int(n / 2) - 1:], int(n / 2) + 1)
else:
return getMedian(arr1[:int(n / 2) + 1],
arr2[int(n / 2):], int(n / 2) + 1)
else:
if n % 2 == 0:
return getMedian(arr1[int(n / 2 - 1):],
arr2[:int(n / 2 + 1)], int(n / 2) + 1)
else:
return getMedian(arr1[int(n / 2):],
arr2[0:int(n / 2) + 1], int(n / 2) + 1)
# function to find median of array
def median(arr, n):
if n % 2 == 0:
return (arr[int(n / 2)] +
arr[int(n / 2) - 1]) / 2
else:
return arr[int(n/2)]
# Driver code
arr1 = [1, 2, 3, 6]
arr2 = [4, 6, 8, 10]
n = len(arr1)
print(int(getMedian(arr1,arr2,n)))
# This code is contributed by
# baby_gog9800
最佳答案
是的,绝对是。许多应聘者在编程面试中因为错过了这一点而得了不好的分数。
在 python 中切片列表会生成一个副本。
复制一半列表需要 O(n) 时间。
这个算法总共需要 O(n) 时间(你应该去弄清楚为什么它不是 O(n log n))
对于任何特定示例,您确实需要了解您的语言如何工作才能弄清楚这一点,因为某些语言提供了在不复制元素的情况下对列表进行切片的方法。在 java 中,您可以调用 list.sublist(start,end)
,例如,无需复制即可获取切片。
关于algorithm - 将数组拆分为 2 个子数组并递归求解它们仍然是 O(log(n))?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/57449839/
不同的 LogCat 方法是: Log.v(); // Verbose Log.d(); // Debug Log.i(); // Info Log.w(); // Warning Log.e();
在android群里,经常会有人问我,android log是怎么用的,今天我就把从网上以及sdk里东拼西凑过来,让大家先一睹为快,希望对大家入门android log有一定的帮助. android
关闭。这个问题是opinion-based 。目前不接受答案。 想要改进这个问题吗?更新问题,以便 editing this post 可以用事实和引文来回答它。 . 已关闭 4 年前。 社区 12
我正在尝试使用 sonarlint 检查代码质量.上面的问题概要,我不明白为什么它要说要大写。但是 this discussion与上述建议相反。哪一个应该被认为是正确的? 最佳答案 这没有正确答案,
随着 n 变大,log*(log n) 和 log(log* n) 这两个函数会更快吗? 这里,log* 函数是迭代对数,定义如下: 我怀疑它们是相同的,只是写法不同,但它们之间有什么区别吗? 最佳答
作为家庭作业,我被要求在 O(log(n)) 中编写一个算法,我可以计算出我编写的算法的复杂度为 O(log(n) + log(n/2) + log(n/4) + log(n/8) + ... + l
我正在使用 Tomee。日志文件夹包含这样的文件 localhost_access_log.2016-12-02.txt localhost.2016-12-02.log catalina.2016-
Android Log.v、Log.d、Log.i、Log.e 等的 ios 等效项是什么?同样在 android 上,我使用 Android 设备监视器和 logcat 来访问我的手机日志,我需要在
我认为下面的代码是 O(log log n) 因为它里面有 i*i 但我对 log n 感到困惑> 和 log (log n)。 for (i=2; i*i<=number; i++) { if
我正在修改 kvm 模块,并在内核代码中添加了 printk 语句。运行虚拟机后,printk 为我提供了错误地址和有关 guest 操作系统的其他信息。 我需要从这个信息中生成统计信息。当我使用 d
我有一个部署为 Windows Azure Web 角色的 WCF 服务。 我正在使用 Enterprise Library 进行异常处理,并且在我的本地 Development Fabric 中,似
关闭。这个问题是opinion-based 。目前不接受答案。 想要改进这个问题吗?更新问题,以便 editing this post 可以用事实和引文来回答它。 . 已关闭 9 年前。 Improv
在 Go 的生产中使用 log.SetFlags(log.LstdFlags | log.Lshortfile) 是好的做法(至少是一般做法)吗?我想知道在生产中这样做是否存在性能或安全问题。因为它不
我想知道什么更快: double value = Math.log(a) - Math.log(b); 或 double value = Math.log(a/b); 我计算值的方式是否会对性能产生影
我有数百个子例程使用 log.Println() 写入日志文件 我正在使用 log.Println 写入 error.log 文件。 func main() { e, err := os.Open
我将 Nuxt 与 SSR 一起使用,并希望有类似于 apaches 的 access.log 和 error.log 的东西 我特别感兴趣的是每次调用的响应时间。 我在 nuxt 文档中找不到任何内
我知道以前有人问过这个问题,但我相信这是一个不同的问题。 Nginx 在 www-data 下运行: $ ps -eo "%U %G %a" | grep nginx root root
我在我的日志文件中发现了一个非常奇怪的条目 Jan 29 01:35:30 vs-proj-handy sshd[5316]: Received disconnect from 130.207.203
对于我正在开发的应用程序,我希望在开发过程中和发布时简化故障排除。我希望能够检索到对 Log 的调用,以了解在 USB 调试中没有连接手机的情况下运行应用程序时的调用,以便可以检索并发送给我。例如,当
我试图捕获 panic 并记录错误: func (s *server) SayHello(ctx context.Context, in *pb.HelloRequest) (*pb.HelloRep
我是一名优秀的程序员,十分优秀!