问题标签 [complexity-theory]

For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.

0 投票
3 回答
278 浏览

algorithm - 无法推断出算法有效性的表格

我不完全确定下表

替代文字 http://files.getdropbox.com/u/175564/algTranslation.png

该表提供了当算法复杂度为给定大小时,可以在左侧列中给出的时间限制内解决的问题大小。

我对表的扣除感兴趣。

这张表告诉我

  • O(n) = 10M 秒(这似乎是当前计算机的能力)
  • n是要处理的项目数#感谢 Guffa!

我不确定如何推导出 O(n * log(n)) 列中的值。

  1. 你如何推断​​出O(n * log(n)) 的值 0.5M 或 O(n^2) 的 3000?
0 投票
8 回答
18493 浏览

sql - 简化 SQL 语句的一般规则

我正在寻找一些“推理规则”(类似于集合操作规则或逻辑规则),我可以使用它们来减少 SQL 查询的复杂性或大小。有没有这样的东西?任何文件,任何工具?您自己找到的任何等效项?它在某种程度上类似于查询优化,但在性能方面不同。

换一种说法:使用 JOIN、SUBSELECT、UNION 进行(复杂)查询是否可以(或不)通过使用一些转换规则将其简化为产生相同结果的更简单、等效的 SQL 语句?

因此,我正在寻找 SQL 语句的等效转换,例如大多数 SUBSELECT 可以重写为 JOIN。

0 投票
3 回答
343 浏览

complexity-theory - 为什么这么严重,呃..复杂?

我只是在这个网站上浏览了一个相关的问题列表,这让我开始思考。我看到很多问题,例如:

  • 我应该使用我的包部署 XYZ 还是添加对其他路径的引用?
  • 如何配置 nant/cruisecontrol/etc.. 来运行我的单元测试?
  • 在 XYZ 设置中,我应该在哪里保存用于单元测试的配置文件
  • ETC...

现在,当我开发(使用 .NET 和 Visual Studio)时,我选择了一个非常具体的目录结构:

  • doc:包含所有文档
  • lib:包含已编译的依赖项
  • src:包含所有程序源和依赖源
  • etc:与项目相关的其他文件
  • bin:编译后的程序输出

一般来说,如果在那个目录结构中不能做某事,我就干脆不做。这包括单元测试、持续集成等......同样,我的整个程序将在 bin 目录之外运行,但操作系统或网络引用除外。我拒绝在不驻留在我的程序根目录中的文件系统上引入依赖项。我确信我错过了一些非常酷的开发方面,但我已经尝试过巡航控制,我已经尝试过 nant,老实说,作为一个从事许多小项目(200 多个小项目)的人一年)相对于几个(10-20)个大型项目,我可以诚实地说,简单性比使用这些工具的一些好处更可取。

我想我的问题是,我只是一个简单的人,还是看起来某些事情比它们需要的复杂得多?整个“设计适合所有人”的心态似乎确实有时会妨碍完成工作。

0 投票
5 回答
113774 浏览

python - len() 函数的成本

len()Python 内置函数的功能成本是多少?(列表/元组/字符串/字典)

0 投票
5 回答
134013 浏览

.net - .NET 控制台应用程序退出事件

在 .NET 中,是否有一种方法(例如事件)来检测控制台应用程序何时退出?我需要清理一些线程和COM对象。

我正在从控制台应用程序运行一个没有表单的消息循环。我正在使用的DCOM组件似乎需要应用程序泵送消息。

我尝试向 Process.GetCurrentProcess.Exited 和 Process.GetCurrentProcess.Disposed 添加一个处理程序。

我还尝试向Application.ApplicationExitApplication.ThreadExit事件添加处理程序,但它们没有触发。也许那是因为我没有使用表格。

0 投票
6 回答
15519 浏览

java - 超越圈复杂度的代码复杂度分析工具

虽然圈复杂度是一个有价值的指标,但我倾向于发现它不是识别难以维护的代码的糟糕工具。特别是,我倾向于发现它只是突出了某些类型的代码(例如解析器),而忽略了困难的递归、线程和耦合问题以及许多已定义的反模式。

还有哪些其他工具可用于识别有问题的 Java 代码?

请注意,我们已经使用了 PMD 和 FindBugs,我认为它们非常适合方法级别的问题识别。

0 投票
11 回答
4343 浏览

programming-languages - 编程语言复杂度

是否有一个编程语言在语法和语义方面的复杂性的客观衡量标准,而不是该语言的使用复杂程度

我读过很多主观评论,但很少有严谨的分析。

0 投票
3 回答
3883 浏览

complexity-theory - 如何使用步数计算时间复杂度

0 投票
3 回答
1793 浏览

complexity-theory - Some Questions on Complexity

1) Reorder the following efficiency from smallest to largest: 2^n, n!, n^5, 10000, nlog2(n)

My Ans-> 10000 < nlog2(n) < n^5 < 2^n < n!

Correct ?

2) Efficiency of an algo. is n^3, if a step in this algo. takes 1 nanosec. (10^-9 sec.). How long does it take the algo. to process an input of size 1000?

I don't know ... Is it (1000)^3 * 10^-9 ?

0 投票
11 回答
5826 浏览

performance - 您是否在“现实世界”中使用 Big-O 复杂度评估?

最近在一次采访中,我被问到几个与技术问题过程中出现的各种算法的 Big-O 相关的问题。我不认为我在这方面做得很好......自从我参加编程课程以来,我们被要求计算算法的 Big-O 十年以来,我没有讨论过任何东西的“Big-O”我工作过或设计过。我与其他团队成员以及与我共事过的架构师就代码的复杂性和速度进行了许多讨论,但我从未加入过在实际项目中实际使用 Big-O 计算的团队。讨论总是“鉴于我们对数据的理解,是否有更好或更有效的方法来做到这一点?” 永远不要“这个算法的复杂性是多少”?

我想知道人们是否真的在讨论他们的代码中的“Big-O”?