将一个数组一分为二并找到整体最小元素的时间复杂度是多少?

是O(n)还是O(logn)?

推荐答案

将一个(未排序的)数组划分为2个已排序分区的复杂度为O(NlogN).

一旦你有了两个已排序的分区,在其中任何一个中找到最小的元素都是O(1)...因此,这两个分区.

(已排序分区的最小元素是第一个.)

Java相关问答推荐

如何在Inspaut中获取当前路径的 * 模式 *?

将@ManyToOne JPA Composite Key用作Id保存实体添加额外参数

当列顺序更改时,Table View列列表的Change. wasPermanted()总是返回假

Android视图覆盖不阻止点击它后面的控件

int Array Stream System. out. print方法在打印Java8时在末尾添加% sign

无法找到符号错误—Java—封装

Java 8中的多个字段和计数

如何以干净的方式访问深度嵌套的对象S属性?

SpringBootreact 式Web应用程序的Spring Cloud Configer服务器中的资源控制器损坏

在Spring Boot中使用哪个Java类来存储创建时间戳?

JOOQ中的子查询使用的是默认方言,而不是配置的方言

带有Health Check的Spring Boot BuildPack打破了本机映像构建过程

虚拟线程应该很快消亡吗?

舰队运行配置Maven版本

Regex以查找不包含捕获组的行

插入中的JOOQ序列,设置为VS值

有没有办法知道在合并中执行了什么操作?

JavaFX,GridPane:在GridPane的列中生成元素将保持所有列的宽度

我无法在我的Spring Boot应用程序中导入CSV依赖项

ReturnedRect在升级后反转