use*_*556 0 algorithm complexity-theory data-structures
我正在我的课堂上研究算法的复杂性,我需要知道算法是否有其他复杂性,我知道和研究的是2种类型1-是BIG O的复杂性,即时间和性能,以及其他2 - 空间复杂性是内存复杂性,算法是否还有其他复杂性？算法是否由我错过的任何其他东西来衡量？
就算法的渐近复杂性而言 - 是的,算法(和问题)是根据空间和时间来衡量的.
但是,我可以说更多.我会尝试解决一些问题:
空间/时间消耗来自分析方法
有四种常用的算法分析方法,用于空间和时间.请记住,big-O是一组函数,但是如何导出函数呢？根据分析方法导出复杂性的功能,该方法通常是以下之一:
这些方法中的每一种都可以用于任何算法 - 并且结果不能保证是相同的.例如,快速排序具有O(n^2)最差的案例时间复杂度和O(nlogn)平均案例时间复杂度.
更多集合:
除了大O表示法之外,我们还使用其他表示法来表示复杂性.其他常用符号(按使用的通用性):
不要与分析方法相混淆:Big Theta/Big O/notations ...中的每一个都可以与任何分析方法配对(最坏情况/平均情况/ ...)
更多关于Big Theta,Big O和它们之间的差异可以在这个帖子中找到
理论复杂性:
在理论"复杂性理论"领域 - 我们分析问题,而不是算法.在这个领域,我们关心一个问题是否可以多项式解决(也就是说,如果输入的大小为n,那么问题可以用n的某些幂来解决),多项式验证(给出一个可能的解决方案,检查它是否是正确).但是,还有其他类.
常见的复杂性类别是:
此外 - 如果问题可以解决/可以解决,我们感兴趣.描述问题可解决性的通用类是:
真实世界:
在现实世界的应用程序中 - 我们不仅关心理论空间/时间复杂性,还关注常量(一种算法占用一半的时间,因为另一种更好,即使它们可以处于相同的复杂性类别.这是因为复杂性类忽略了常量.
我们还考虑了程序/算法的实现时间和可维护性.