算法复杂度的衡量标准:大O表示法
发布时间:2020-12-16 07:36:16 所属栏目:百科 来源:网络整理
导读:学习 C++ 标准库,特别是 STL,经常需要考量算法和成员函数的效能(也就是运行效率,又称 复杂度 ),因此每个学习 STL 的读者都需要掌握一种衡量算法(或成员函数)复杂度的方法,目前最常用的方法称为 大 O 表示法 (注意,不是数字 0,而是字母 O)。 使用
学习 C++ 标准库,特别是 STL,经常需要考量算法和成员函数的效能(也就是运行效率,又称复杂度),因此每个学习 STL 的读者都需要掌握一种衡量算法(或成员函数)复杂度的方法,目前最常用的方法称为大 O 表示法(注意,不是数字 0,而是字母 O)。 使用大 O 表示法衡量某个算法的复杂度,其实就是将该算法的运行时间用输入量为 n 的函数表示出来。这里的输入量 n 在 STL 中通常指的是算法操作的元素个数。 举个例子,当算法运行时间随元素个数成线性增长时(即如果元素个数呈倍数增长,运行时间也呈倍数增长),该算法的复杂度用 O(n) 来表示;反之,如果算法的运行时间和输入量 n 无关,则该算法的复杂度就用 O(1) 来表示。 表 1 列出了常见的算法复杂度种类,以及使用大 O 表示法表示的复杂度。
值得注意的是,大 O 表示法并不关心算法运行所消耗的具体时间,换句话说,对于那些影响算法运行效率较小的因素,使用大 O 表示法表示时会直接将其忽略。例如,某个算法运行的复杂度为 O(n),呈线性增长,但至于线性增长的具体程度(是 100n 还是 2n),在大 O 表示法看来,它们是一样的。也就是说,采用这种测量法则,任何两个线性算法都将被视为具有相同的复杂度。 所以请读者记住,大 O 表示法只是某种度量方法,它所显示的算法的最佳复杂度,并不一定就是真正的最佳(最快)算法。
表 2 列出了常用的复杂度随元素个数增长的变化程序。可以看到,当算法处理的元素较少时,各复杂度的差别很小,此时算法效率的优劣往往受被大 O? 表示法忽略部分的影响更大。而当处理元素个数越多,各复杂度的差别越大,此时复杂度被忽略的部分就变得无关紧要了。 因此,在考量算法的复杂度时,输入量 n (操作元素的个数)的值必须足够大才有意义。 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |