草庐IT

c++ - "constant"复杂度的真正含义是什么？时间？复制/移动的数量？

coder 2023-11-13 原文

就目前而言，这个问题不适合我们的问答形式。我们希望答案得到事实、引用或专业知识的支持，但这个问题可能会引起辩论、争论、投票或扩展讨论。如果您觉得这个问题可以改进并可能重新打开，visit the help center为指导。




9年前关闭。




我可以想到 C++ 中的三个操作，它们在某种意义上可以被描述为具有“恒定”的复杂性。我已经看到一些关于这意味着什么的争论(*)，在我看来，我们可以说“所有这些操作都是恒定的，但有些比其他操作更恒定”:-)

( 编辑 2 : 如果您已经认为自己知道答案，请在过早进入之前阅读此问题的一些辩论:What data structure, exactly, are deques in C++? 很多得分很高的人正在争论什么'常数'的意思。我的问题并不像你想象的那么明显!)

( 编辑 :我不需要了解“复杂性”的含义。我想要一个明确的答案，也许是来自 C++ 标准的引号，它告诉我们什么应该是恒定的。处理器滴答声，真实世界的时间，还是其他什么？在其他线程上，有些人认为时间与 C++ 标准的要求完全无关。)

标准中的这些复杂性保证是否适用于操作的运行时？或者他们是否只是指定了所包含对象可能发生的(最大)复制/移动次数？ “摊销”究竟是什么意思？

1. 给定一个(非空)vector<int> v ，以下在运行时显然是恒定的:

swap(v.front(), v.back());

(尽管学究可能会指出这取决于数据是在缓存中还是换出或其他什么!)。

2. 给定一个 list<int> l ，做一个 push_back很简单。恰好分配了一个新项目，并打乱了链表中的一些指针。每个 push_front 都涉及一个分配，总是具有相同的内存量，因此这显然是相当“恒定”的。但是，当然，进行分配的时间可能会有很大差异。内存管理可能需要花费大量时间才能找到一些合适的空闲内存。

3. 但是做一个push_back在 vector<int>更是难以预料。大多数情况下，它会非常快，但它必须时不时地为所有数据重新分配空间并将每个元素复制到新位置。因此，它在运行时的可预测性不如单个 list::push_front ，但它仍然被称为常数(摊销)。平均而言，向一个 vector 添加大量数据将需要一个与添加量无关的复杂性，这就是为什么它被称为“摊销常数”时间。 (我对吗？)

最后，我问了 int以避免具有另一种类型的复杂性。例如，vector< vector<int> >推理可能有点复杂，因为( vector 的) vector 的每个元素可能具有不同的大小，例如，交换两个元素并不像 那样恒定。 1. 以上。但理想情况下，我们可以回答所有 vector<T> ，不仅仅是 T=int .

(*) 有关辩论的示例，请参阅对这些答案的评论:What data structure, exactly, are deques in C++?

最佳答案

复杂性总是相对于特定变量或变量集来表述的。因此，当标准谈论恒定时间插入时，它谈论的是相对于列表中项目数量的恒定时间。也就是说，O(1) 次插入意味着当前列表中的项数不影响插入的整体复杂度。列表中可能有 500 或 50000000 个项目，插入操作的复杂度将相同。

例如，std::list有 O(1) 次插入和删除；插入的复杂性不受列表中元素数量的影响。然而，内存分配器的复杂性很可能取决于已经分配的东西的数量。但是由于 O(1) 是在谈论列表中的项目数，因此它不包括在内。也不应该，因为那样我们将测量内存分配器的复杂性，而不是数据结构。

简而言之:这是一个不同的衡量标准。

It implies that we are free to implement our algorithm as badly as we like, including one where the time isn't really constant in any pragmatic sense, but where we have respected the number of 'operations' on the contained objects.



未指定相对于实现的复杂性。它是相对于算法指定的。上下文可以切换并不重要，因为运行时间不是复杂性的原因。

如上，你可以实现 std::list使用一个内存分配器，对于删除操作是 O(log(n))(其中 n 是分配的数量)。但是，相对于列表中的项目数，删除列表中的元素仍然是 O(1)。

不要将复杂性与整体性能混淆。复杂性的目的是针对不同变量的算法有一个通用度量。希望他们的代码快速运行的程序员的目的是找到一个算法的合理实现，该算法符合他们实现该性能所需的复杂性。

复杂性是评估算法效率的工具。复杂性并不意味着您可以停止思考。

And what exactly does 'amortized' mean?



Amortized这意味着:

如果某事是“摊销 X 时间”，那么当您在同一数据结构上无限次重复操作时，X 处的复杂性限制。

所以，std::vector在后面插入了“摊销固定时间”。因此，如果我们取对象并对其执行无限次插入，则复杂性的渐近极限将与“恒定时间”插入没有什么不同。

通俗地说，就是操作有时可能是非常数的，但是非常数的次数会一直递减。在长期的插入过程中，时间是恒定的。

关于c++ - "constant"复杂度的真正含义是什么？时间？复制/移动的数量？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/8631531/

amp含义codebr恒定c++complexity-theorytime-complexity

有关c++ - "constant"复杂度的真正含义是什么？时间？复制/移动的数量？的更多相关文章

  1. ruby - 为什么我可以在 Ruby 中使用 Object#send 访问私有(private)/ protected 方法？ - 2

    类classAprivatedeffooputs:fooendpublicdefbarputs:barendprivatedefzimputs:zimendprotecteddefdibputs:dibendendA的实例a=A.new测试a.foorescueputs:faila.barrescueputs:faila.zimrescueputs:faila.dibrescueputs:faila.gazrescueputs:fail测试输出failbarfailfailfail.发送测试[:foo,:bar,:zim,:dib,:gaz].each{|m|a.send(m)resc

  2. ruby-on-rails - rails : "missing partial" when calling 'render' in RSpec test - 2

    我正在尝试测试是否存在表单。我是Rails新手。我的new.html.erb_spec.rb文件的内容是:require'spec_helper'describe"messages/new.html.erb"doit"shouldrendertheform"dorender'/messages/new.html.erb'reponse.shouldhave_form_putting_to(@message)with_submit_buttonendendView本身，new.html.erb，有代码:当我运行rspec时，它失败了:1)messages/new.html.erbshou

  3. ruby-on-rails - 由于 "wkhtmltopdf"，PDFKIT 显然无法正常工作 - 2

    我在从html页面生成PDF时遇到问题。我正在使用PDFkit。在安装它的过程中，我注意到我需要wkhtmltopdf。所以我也安装了它。我做了PDFkit的文档所说的一切......现在我在尝试加载PDF时遇到了这个错误。这里是错误:commandfailed:"/usr/local/bin/wkhtmltopdf""--margin-right""0.75in""--page-size""Letter""--margin-top""0.75in""--margin-bottom""0.75in""--encoding""UTF-8""--margin-left""0.75in""-

  4. ruby-on-rails - Rails - 子类化模型的设计模式是什么？ - 2

    我有一个模型:classItem项目有一个属性“商店”基于存储的值，我希望Item对象对特定方法具有不同的行为。Rails中是否有针对此的通用设计模式？如果方法中没有大的if-else语句，这是如何干净利落地完成的？ 最佳答案 通常通过Single-TableInheritance. 关于ruby-on-rails-Rails-子类化模型的设计模式是什么？，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.co

  5. ruby-on-rails - Ruby on Rails : . 常量化 : wrong constant name error? - 2

    我正在使用这个:4.times{|i|assert_not_equal("content#{i+2}".constantize,object.first_content)}我之前声明过局部变量content1content2content3content4content5我得到的错误NameError:wrongconstantnamecontent2这个错误是什么意思？我很确定我想要content2=\ 最佳答案 你必须用一个大字母来调用ruby​​常量:Content2而不是content2。Aconstantnamestart

  6. ruby - 什么是填充的 Base64 编码字符串以及如何在 ruby​​ 中生成它们？ - 2

    我正在使用的第三方API的文档状态:"[O]urAPIonlyacceptspaddedBase64encodedstrings."什么是“填充的Base64编码字符串”以及如何在Ruby中生成它们。下面的代码是我第一次尝试创建转换为Base64的JSON格式数据。xa=Base64.encode64(a.to_json) 最佳答案 他们说的padding其实就是Base64本身的一部分。它是末尾的“=”和“==”。Base64将3个字节的数据包编码为4个编码字符。所以如果你的输入数据有长度n和n%3=1=>"=="末尾用于填充n%

  7. ruby - 解析 RDFa、微数据等的最佳方式是什么，使用统一的模式/词汇(例如 schema.org)存储和显示信息 - 2

    我主要使用Ruby来执行此操作，但到目前为止我的攻击计划如下:使用gemsrdf、rdf-rdfa和rdf-microdata或mida来解析给定任何URI的数据。我认为最好映射到像schema.org这样的统一模式，例如使用这个yaml文件，它试图描述数据词汇表和opengraph到schema.org之间的转换:#SchemaXtoschema.orgconversion#data-vocabularyDV:name:namestreet-address:streetAddressregion:addressRegionlocality:addressLocalityphoto:i

  8. ruby - 为什么 4.1%2 使用 Ruby 返回 0.0999999999999996？但是 4.2%2==0.2 - 2

    为什么4.1%2返回0.0999999999999996？但是4.2%2==0.2。 最佳答案 参见此处:WhatEveryProgrammerShouldKnowAboutFloating-PointArithmetic实数是无限的。计算机使用的位数有限(今天是32位、64位)。因此计算机进行的浮点运算不能代表所有的实数。0.1是这些数字之一。请注意，这不是与Ruby相关的问题，而是与所有编程语言相关的问题，因为它来自计算机表示实数的方式。 关于ruby-为什么4.1%2使用Ruby返

  9. ruby - 检查 "command"的输出应该包含 NilClass 的意外崩溃 - 2

    为了将Cucumber用于命令行脚本，我按照提供的说明安装了arubagem。它在我的Gemfile中，我可以验证是否安装了正确的版本并且我已经包含了require'aruba/cucumber'在'features/env.rb'中为了确保它能正常工作，我写了以下场景:@announceScenario:Testingcucumber/arubaGivenablankslateThentheoutputfrom"ls-la"shouldcontain"drw"假设事情应该失败。它确实失败了，但失败的原因是错误的:@announceScenario:Testingcucumber/ar

  10. ruby-on-rails - 如何优雅地重启 thin + nginx？ - 2

    我的瘦服务器配置了nginx，我的ROR应用程序正在它们上运行。在我发布代码更新时运行thinrestart会给我的应用程序带来一些停机时间。我试图弄清楚如何优雅地重启正在运行的Thin实例，但找不到好的解决方案。有没有人能做到这一点？ 最佳答案 #Restartjustthethinserverdescribedbythatconfigsudothin-C/etc/thin/mysite.ymlrestartNginx将继续运行并代理请求。如果您将Nginx设置为使用多个上游服务器，例如server{listen80;server

随机推荐