时间戳

首页 > 解决方案 > 运行时间为 O(n^2 log n) 的算法示例？

algorithm - 运行时间为 O(n^2 log n) 的算法示例？

问题描述

我必须构建一个算法，其上限为 O(n 2 log n)。任何人都可以提供任何关于 O(n 2 log n) 算法的示例吗？我似乎无法绕开它。

我对它的印象是两个嵌套的 for 循环，在第二个循环中执行 log n 操作。这个对吗？

标签： algorithmbig-o

解决方案

从技术上讲，任何渐近速度快于的算法n^2 log n都称为O(n^2 log n). 示例包括“什么都不做”算法Theta(1)、二分搜索Theta(log n)、线性搜索Theta(n)、冒泡排序Theta(n^2)。

您描述的算法O(n^2 log n)也是Omega(n^2 log n)如此，因此Theta(n^2 log n)：

for i in range(n):
    for j in range(n):
        # binary search in array of size n

推荐阅读