数学吧 关注:916,892贴子:8,843,536
  • 8回复贴,共1

一点关于运算的时间复杂度问题

只看楼主收藏回复

前排提示:不许单纯回答O(n),必须表示为具体的多项式!
设int a和 int b(且两数字均不为0),两个数字在k进制下表示的长度分别为m和n。
求这两个数字进行以下操作时的时间复杂度:
1.加法和减法
2.乘法和除法
3.求乘方和对数(a^b和b^a分开)。
4.如果可以,尽可能补充其他运算


IP属地:上海来自Android客户端1楼2024-03-11 13:21回复
    题目表述不清啊,你说不要用O(n),那你是想要Ω或者Θ,或者是什么别的?


    IP属地:浙江来自Android客户端2楼2024-03-11 15:28
    收起回复
      2025-08-05 03:28:10
      广告
      不感兴趣
      开通SVIP免广告
      好奇具体时间?
      那你要去研究编译器搞出来的指令,然后找到cpu的物理设计,对着指令研究具体实现
      如果不够,还要去考虑主板内存的电路设计,看看缓存命中率
      我劝你放弃


      IP属地:北京来自Android客户端3楼2024-03-13 09:01
      回复
        时间复杂度一般不讨论常数,1和2是O(1),3是O(logn)(快速幂)


        IP属地:重庆来自Android客户端5楼2024-03-13 18:01
        回复
          问一下,如果一个算法非常的差,那它的空间复杂度与时间复杂度是什么样的啊?


          IP属地:四川来自Android客户端6楼2024-04-17 18:43
          回复