log(n) * log(log(n)) 的渐近复杂度

Question

昨晚我正在解决一个问题，我不得不 n 次插入优先级队列。因此，渐近复杂度为 n log n。但是 n 可能大到 10^16，所以我必须做得更好。我找到了一个解决方案，它允许我只需要将日志插入优先级队列 n 次，而其他所有内容都保持恒定时间。所以，复杂度是 log(n) * log(log(n))。这是我的渐近复杂性还是可以进一步简化？

这是算法。我能够通过使用哈希图计算将插入优先级队列的重复优先级并基于此提供单一计算来降低复杂性。

根据我的代码，我知道如何将 n log n 复杂性降低到 log n log log n 可能并不直观。我不得不通过示例来弄清楚它 n 被减少到 log n。虽然 solvedUpTo 过去以与 n 相同的速率增加，但现在 ~n<=20 有一半的步骤可以在 solvedUpTo 中达到相同的值，~n<=30 有 1/3 的步骤，之后很快是步数的 1/4 等等（都是近似值，因为我不记得确切的数字）。

代码故意使其解决的问题不明确：

fun  solve(n:Long, x:Long, y:Long): Long {

    val numCount = mutableMapOf<Long,Long>()

    val minQue: PriorityQueue<Long> = PriorityQueue<Long>()

    addToQueue(numCount,minQue,x,1)
    addToQueue(numCount,minQue,y,1)

    var answer = x + y

    var solvedUpTo = 2L

    while (solvedUpTo < n) {

        val next = minQue.poll()

        val nextCount = numCount.remove(next)!!

        val quantityToSolveFor = min(nextCount,n - solvedUpTo)

        answer = ((answer + ((next + x + y) * quantityToSolveFor))).rem(1000000007)

        addToQueue(numCount,minQue,next + x,quantityToSolveFor)
        addToQueue(numCount,minQue,next + y,quantityToSolveFor)

        solvedUpTo += quantityToSolveFor
    }

    return answer
}

fun <K> addToQueue(numCount: MutableMap<K,Long>, minQue: PriorityQueue<K>, num: K, incrementBy: Long) {

    if (incrementMapAndCheckIfNew(numCount, num, incrementBy)) {
        minQue.add(num)
    }
}

//Returns true if just added
fun <K> incrementMapAndCheckIfNew(map: MutableMap<K,Long>, key: K, incrementBy: Long): Boolean {

    val prevKey = map.putIfAbsent(key,0L)

    map[key] = map[key]!! + incrementBy

    return prevKey == null
}

Answer 1

不，O(log n log log n) 与该表达式将得到的一样简单。您有时会在数论上下文中看到像 O(n log n log log n) 这样的运行时间，并且没有更简单的通用函数可以与这些数量等效。

log(n) * log(log(n)) 的渐近复杂度

Asymptotic complexity of log(n) * log(log(n))

math

complexity-theory

big-o