关于两个函数大O时间复杂度判定的疑问：与参考解答存在分歧

Hey there! Let's unpack this complexity disagreement—since you didn't share the actual code for functions b and c, I'll walk through the most common scenarios that lead to these conflicting conclusions, which should help you align with your specific functions.

Function b: O(log n) vs O(n log n) #

The split here almost always comes down to whether the function uses single-branch recursion or multi-branch divide-and-conquer:

• If your reasoning is based on a function like binary search (only recursing on one half of the problem each time, with no linear overhead per call), you're right about O(log n):

  def func_b(n):
      if n <= 1:
          return
      # Only process one half, no linear work here
      func_b(n // 2)
  

  Here, the recursion depth is log₂n, and each call does O(1) work—total complexity is definitely O(log n).
• But if the function uses a divide-and-conquer approach where it processes all subproblems plus does linear work per level (like merge sort), the manual's O(n log n) is correct:

  def func_b(n):
      if n <= 1:
          return
      # Recurse on both halves
      func_b(n // 2)
      func_b(n // 2)
      # O(n) work to merge/combine results
      for _ in range(n):
          pass
  

  Each level of recursion does O(n) total work, and there are log n levels—multiply those together, and you get O(n log n). Chances are you missed the dual recursion or linear per-level work in your analysis.

Function c: O(√n) vs O(n log n) #

This one's trickier, but let's break down the two common cases:

• If your reasoning comes from a function that either loops up to √n or reduces the problem size by taking the square root each time (like finding all divisors of n), O(√n) makes sense:

  def func_c(n):
      count = 0
      # Loop runs √n times, O(1) per iteration
      for i in range(1, int(n**0.5) + 1):
          if n % i == 0:
              count += 2
  

  Or a recursion that shrinks the problem size exponentially via square roots:

  def func_c(n):
      if n <= 2:
          return
      func_c(int(n**0.5))
  

  Here, the recursion depth is effectively negligible compared to √n—so total complexity is O(√n) for the loop example.
• The manual's O(n log n) conclusion likely applies to a function that uses a divide-and-conquer structure with linear work per level, even if it seems like it's dealing with square roots. For example, a variant of merge sort where you're doing linear work across log n levels, but you misinterpreted the subproblem size as √n instead of a constant fraction of n. Another possibility is a function that runs O(n) operations, each taking O(log n) time, which totals O(n log n)—you might have mistaken the per-operation cost for the number of operations.

Final Takeaway #

The key issue here is that complexity depends entirely on the specific operations the function performs, not just high-level structure. Double-check:

• For function b: Does it recurse on one half or all halves? Is there linear work done at each recursion level?
• For function c: Is it a simple loop over √n elements, or does it involve repeated linear work across multiple levels of recursion?

Once you map those details back to your actual functions, you'll see which conclusion fits.

内容的提问来源于stack exchange，提问作者AinGLaw