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

Question

我昨晚解决了一个问题，我不得不n次插入到一个优先级队列中。因此，渐近复杂度是large。然而，n可以达到10^16，所以我必须做得更好。我找到了一个解决方案，它允许我只需插入优先级队列log n次，而其他所有东西都保持恒定时间。因此，复杂度是log(n) * log(log(n))。这是我的渐近复杂度，还是可以进一步简化？

下面是算法。我能够通过使用hashmap来计算插入到优先级队列中的重复优先级，并在此基础上提供单个计算，从而降低复杂性。

我从我的代码中知道，如何将not的复杂度降低到log，这可能并不直观。我不得不通过示例来计算出n是如何减少到log的。虽然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)这样的运行时，并且没有更简单的通用函数可以与这些数量等价。