奇葩面试题,O(logn)的底数是多少?

简介: 奇葩面试题,O(logn)的底数是多少?

大家好,我是老三,最近裸辞了,在面试。

前两天一个面试,只面了十分钟就结束了——

事情是这样的:

面试官:你能说说HashMap的数据结构吗?

老三:数组+链表+红黑树,阿巴阿巴……

面试官:那你说说红黑树的查找复杂度是多少?

老三:O(logn)。

面试官:那这个复杂度的底数是多少?

老三:时间复杂度O(logn)有底数?

面试官:没有吗?

尬住……

面试官:那你再说一下快速排序的时间复杂度?底数是多少?

老三露出智(尴)慧(尬)的微笑……

面试官:好了,我没什么要问的了,这次面试到这结束吧。


结束面试之后,老三意难平,赶紧查一下。

O(logn)是有底数的!

看一下时间复杂度的定义:

在进行算法分析时, 语句总的执行次数 T ( n ) 是关于问题规模 n 的 函 数 。 进 而 分 析 T ( n ) 随 n  的变化情况并确定 T ( n ) 的 数 量级。 算法的时间复杂度,也就是算法的时间量度, 记作: T ( n )=  O(f(n))。它表示随问题规模 n 的增大, 算法执行时间的增长率和f ( n ) 的增长率相同, 称作算法的渐近时间复杂度,  简称为时间复杂度。 其中 f ( n ) 是问题规模 n 的某个函数。

有点抽象对不对,直接上例子,我们来意会一下。

        int n=10;
        int count=1;
        while (count<n){
            count=count*2;
            //时间复杂度为O(1)的运算
            System.out.println(count);
        }

看一下,这个运算,每次 count 乘以 2 之后, 就距离n更近了一分。 也就是说:

破案了,O(logn)确实是有底数的。

这个底数是由什么决定的呢?

算法中log级别的时间复杂度都是由于使用了分治思想,这个底数直接由分治的复杂度决定。如果采用二分法,那么就会以2为底,,三分法就会以3为底数,其他类似。

O(logn)底数意义不大!

那问题来了,为什么我们平时不写底数呢?

总不能因为这个底数太难打吧……

我们注意到,时间复杂度的定义: T ( n )= O(f(n))。它表示随问题规模 n 的增大, 算法执行时间的增长率和f ( n ) 的增长率相同, 称作算法的渐近时间复杂度,简称时间复杂度。

假如说我们要比较两个函数f(n)和g(n)的增长快慢,用什么办法呢?

可以使用微积分里的极限:

image.png

老三高数忘完了哈哈,不会推导,总之最后的结果是一个常数。

也就是,假如n非常大的时候,任意底数的一个对数函数都只是相差一个常数倍而已。

所以无论底数是什么,log级别的渐进意义是一样的。也就是说该算法的时间复杂度的增长与处理数据多少的增长的关系是一样的。

总之:O(logn)已经可以表达所有底数的对数了


花了一个小时,无用的知识又增加了。

简单总结,就是O(logn)有底数,但是没有纠结的必要。

目录
相关文章
|
关系型数据库 MySQL PostgreSQL
MySQL和PostgreSQL的常用语法差异
背景 在去年的DBMS评比中,PostgreSQL夺冠,PostgreSQL一直保持上升姿态,越来越多的客户选择使用PostgreSQL,还有一部分客户从MySQL迁往PostgreSQL,那PostgreSQL和MySQL对于开发者来说的差异在哪里呢?末学对比了下语法差异,不一样的地方用红色标记了出来,供大家参考。
13731 0
halcon算子模板匹配(一)基于形状的模板匹配
halcon算子模板匹配(一)基于形状的模板匹配
2910 0
|
XML 安全 Java
Spring高手之路19——Spring AOP注解指南
在本文中,我们将深入探索Spring AOP(面向切面编程)的核心概念及其在现代Spring应用中的实际应用。从基本的注解使用到复杂的切面配置,本文将一步步指导你如何利用Spring AOP提升代码的模块化,帮助你在Spring开发路上更进一步。
224 3
Spring高手之路19——Spring AOP注解指南
|
11月前
|
存储 IDE Java
Java“NoClassDefFoundError”解决
Java中的“NoClassDefFoundError”错误通常发生在尝试访问某个类时,该类在编译时可用但在运行时找不到。解决方法包括:确保所有依赖库已正确添加到类路径中,检查类名和包名是否正确,以及清理并重新构建项目。
2048 3
|
11月前
|
数据处理 iOS开发 MacOS
Python 虚拟环境安装使用(Anaconda 实操完整版)
【10月更文挑战第4天】Anaconda 是一个开源的 Python 发行版,集成了常用科学计算与数据处理库,并提供了方便的包管理工具 `conda`。虚拟环境则允许在同一台机器上创建多个独立的 Python 运行环境,避免库版本冲突。通过下载 Anaconda、创建与激活虚拟环境、安装软件包及管理环境,可有效支持 Python 项目开发。
1881 8
|
消息中间件 NoSQL Java
2024年高频Java面试题集锦(含答案),让你的面试之路畅通无阻!
或许这份面试题还不足以囊括所有 Java 问题,但有了它,我相信你一定不会“败”的很惨,因为有了它,足以应对目前市面上绝大部分的 Java 面试了,因为这篇文章不论是从深度还是广度上来讲,都已经囊括了非常多的知识点了。
|
JavaScript 前端开发 Java
原型对象和类之间的区别是什么
【8月更文挑战第2天】原型对象和类之间的区别是什么
170 8
|
11月前
|
SQL Java 数据库连接
SPL介绍
【10月更文挑战第5天】
|
机器学习/深度学习 人工智能 监控
基于YOLOv8深度学习的葡萄病害智能诊断与防治系统【python源码+Pyqt5界面+数据集+训练代码】深度学习实战
基于YOLOv8深度学习的葡萄病害智能诊断与防治系统【python源码+Pyqt5界面+数据集+训练代码】深度学习实战
|
机器学习/深度学习 人工智能 自然语言处理
利用深度学习提升语音识别准确率的技术探讨
传统的语音识别技术在面对复杂的语音场景时常常表现出准确率不高的问题。本文探讨了如何利用深度学习技术,特别是深度神经网络,来提升语音识别的精度。通过分析深度学习在语音处理中的应用以及优势,我们展示了如何结合最新的研究成果和算法来解决现有技术的局限性,进一步推动语音识别技术的发展。 【7月更文挑战第3天】
830 0

热门文章

最新文章