许多答案或多个参数情况下的计算复杂性 [英] Computational complexity for the case of many answers or multiple parameters

问题描述

如果算法如下，如何定义计算复杂度？

How is computational complexity defined if the algorithm:

• ...产生许多结果？总数（然后产生一个 k 的算法不能快于 O（k））或每个元素（然后将估计值乘以将其与非设定产生算法进行比较）？
  
  
  
  
  • 存储复杂性如何？估计是否反映出整个集合是否需要一次出现在内存中，或者每个连续的元素都可以产生并丢弃？ / li>
    
  • ...yields many results? As a total (then an algorithm producing a set of k cannot be faster than O(k) ) or per element (then the estimate must be multiplied to compare it with non-set-producing algorithms)?
    • What about storage complexity - does an estimate reflect if the entire set needs to be present in memory at once or each consecutive element can be produced and discarded?

    适合这两种情况的示例是从 N中选择 k 个元素。例如。根据是否需要〜k 或〜N 个步骤，估算值是否有所不同？

    An example that suits both cases is selecting k elements from N. E.g. is there a difference in the estimate depending on whether ~k or ~N steps are required?

    我想看到一些确凿的证据：在这些情况下，该术语的正式定义和/或在CS论文中如何消除这些歧义，而不仅仅是随意的想法和/或个人经验。我们的目标是制定出一套完整的最新解决方案，以一劳永逸地消除我（和其他人）文本中的这些歧义。

    I'd like to see some hard evidence: the formal definition of the term in these cases and/or how these ambiguities are eliminated in CS papers rather than just random thoughts and/or personal experience. The goal is to work out a complete, state-of-the-art solution to eliminate these ambiguities in my (and others') texts once and for all.

    <子>令我感到困惑的问题是： O（1）中的唯一（非重复）随机数？，如何有效地生成一个K值（介于0和上限N之间）的K个非重复整数的列表，选择一个随机组合值的算法？，从链接的对象中有效选择一组随机元素ist 。

    _{The questions that had me puzzled about this are: Unique (non-repeating) random numbers in O(1)?, How do you efficiently generate a list of K non-repeating integers between 0 and an upper bound N, Algorithm to select a single, random combination of values?, Efficiently selecting a set of random elements from a linked list.}

    推荐答案

    根据CS.SE的答案：

    
    
    • 时间复杂度和空间复杂度应分别报告每个变量： O（k）和 O（n ）时间， O（1）空间。
      
      
      
      
      • 如果时间/空间不取决于某些变量，但不是全部，则可以用纯文本或类似的形式来表示。为简洁起见，O（n ⁰ ）（此处没有通用约定）
      
      
      • Time complexity and space complexity shall be reported separately and separately for each variable: "O(k) and O(n) time, O(1) space".
        • If the time/space doesn't depend on some of the variables but not all, this can be told in plain text or with something like O(n⁰) for brevity (there's no universal convention here)
        
        
        • 对于流算法，其 delay 也可以描述为：
          
          
        • For a streaming algorithm, its delay can also be described:

        
        

        例如，一个 O（log n）延迟算法在
        时间返回一个结果，最多执行 O（log n）个步骤（运行时间）以输出每个
        结果。

        For instance, a O(log n) delay algorithm returns results one at a time, taking at most O(log n) steps (running time) to output each result.

      
      

      这篇关于许多答案或多个参数情况下的计算复杂性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！