洛恩实际上是什么意思？

发布于 2024-11-04 05:14:07 字数 443 浏览 2 评论 0原文

我正在学习算法课，一直在研究 QuickSort。我了解该算法及其工作原理，但不了解如何获取它进行的比较次数，或者 logn 最终的实际含义。

我了解基础知识，达到以下程度：

x=logb(Y) then
b^x = Y

但这对于算法性能意味着什么？这是你需要做的比较的数量，我明白......整个想法看起来是如此难以理解。与 QuickSort 类似，每个 K 级调用都涉及 2^k 次调用，每个调用都涉及长度为 n/2^K 的子列表。

因此，求和即可找到比较次数：

log n
Σ 2^k. 2(n/2^k) = 2n(1+logn)
k=0

为什么我们求和为 log n 吗？ 2n(1+logn) 从哪里来？抱歉我的描述含糊不清，我只是很困惑。

原文

I am just studying for my class in Algorithms and have been looking over QuickSort. I understand the algorithm and how it works, but not how to get the number of comparisons it does, or what logn actually means, at the end of the day.

I understand the basics, to the extent of :

x=logb(Y) then
b^x = Y

But what does this mean in terms of algorithm performance? It's the number of comparisons you need to do, I understand that...the whole idea just seems so unintelligible though. Like, for QuickSort, each level K invocation involves 2^k invocations each involving sublists of length n/2^K.

So, summing to find the number of comparisons :

log n
Σ 2^k. 2(n/2^k) = 2n(1+logn)
k=0

Why are we summing up to log n ? Where did 2n(1+logn) come from? Sorry for the vagueness of my descriptions, I am just so confused.

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

不可一世的女人 2024-11-11 05:14:07

如果考虑一棵完整的平衡二叉树，那么逐层就有 1 + 2 + 4 + 8 + ... 顶点。如果树中的顶点总数为 2^n - 1，那么逐层计数就有 1 + 2 + 4 + 8 + ... + 2^(n-1) 个顶点。现在，令 N = 2^n （树的大小），则树的高度为 n，并且 n = log2(N) （树的高度）。这就是 log(n) 在这些 Big O 表达式中的含义。

回复收藏 0 原文

夏日落 2024-11-11 05:14:07

下面是一个示例树：

      1
    /   \ 
   2     3
  / \   / \
 4   5 6   7

树中的节点数为 7，但树的高度为 log 7 = 3，当你有分而治之的方法时，log 就会出现，在快速排序中，你将列表分成 2 个子列表，并继续这个直到丰富的小列表，除法需要 logn 时间（平均情况下），因为除法的最高位是 log n，每个级别的分区需要 O(n)，因为平均每个级别你划分了N个数字，（可能也有许多列表用于分区，但每个级别的平均数字数量为 N，实际上某些列表的数量为 N）。因此，为了简单观察，如果您有平衡分区树，您就有 log n 时间进行分区，这意味着树的高度。

below is a sample tree:

      1
    /   \ 
   2     3
  / \   / \
 4   5 6   7

number of nodes in tree is 7 but high of tree is log 7 = 3, log comes when you have divide and conquer methods, in quick sort you divide list into 2 sublist, and continue this until rich small lists, divisions takes logn time (in average case), because the high of division is log n, partitioning in each level takes O(n), because in each level in average you partition N numbers, (may be there are too many list for partitioning, but average number of numbers is N in each level, in fact some of count of lists is N). So for simple observation if you have balanced partition tree you have log n time for partitioning, which means high of tree.

回复收藏 0 原文

时光沙漏 2024-11-11 05:14:07

1 在这里忘记 b 树

'数学：log2 N = k 是相同的 2^k=N .. 它是 log 的定义
，它可以是自然 log(e) N = k 又名 e^k = n，或十进制 log10 N = k 是 10^k = n

2 参见完美的平衡树

1
1+1
1 + 1 + 1+ 1
8个
16个
等等

有多少个元素？ 1+2+4+8..etc ，所以对于 2 级 b 树有 2^2-1 个元素，对于 3 级树有 2^3-1 等。所以这里有一个神奇的公式： N_TREE_ELEMENTS= 级别数^ 2 -1 ，或使用 log 的定义： log2 number OF level= number_of_tree_elements （可以忘记 -1 ）

3 假设有一个任务在 N 个元素 b 树中查找元素，w/ K 层（又名高度），

其中如何b-tree 的构造是 log2 height = number_of_tree elements

最重要的，

因此通过 b-tree 的构造方式，您不需要更多的“height”操作来查找所有 N 个元素中的元素，或者更少......所以高度等于：log2 number_of_tree_elements。所以

你需要 log2 N_number_of_tree_elements.. 或 log(N) 更短

回复收藏 0 原文

烂人 2024-11-11 05:14:07

要了解 O(log(n)) 的含义，您可能需要阅读 Big O notaion。在镜头中，这意味着，如果您的数据集增大 1024 倍，则运行时间只会延长 10 倍（或更少）（对于基数 2）。

MergeSort 的运行时间为 O(n*log(n))，这意味着它将花费 10240 倍的时间。冒泡排序的运行时间为 O(n^2)，这意味着需要 1024^2 = 1 048 576 倍长。因此，确实有一些时间是安全的:)

要理解您的总和，您必须将合并排序算法视为一棵树：

         sort(3,1,2,4)
        /            \
   sort(3,1)      sort(2,4)
    /     \        /     \
sort(3) sort(1) sort(2) sort(4)

总和会迭代树的每个级别。 k=0 是顶部，k= log(n) 是底部。树的高度始终为 log2(n) （因为它是平衡的二叉树）。

做一些数学计算：

Σ 2^k * 2(n/2^k) = 
2 * Σ 2^k * (n/2^k) =
2 * Σ n*2^k/2^k = 
2 * Σ n = 
2 * n * (1+log(n)) //As there are log(n)+1 steps from 0 to log(n) inclusive

这当然需要做很多工作，特别是如果您有更复杂的算法。在这些情况下，您会对主定理感到非常高兴，但目前它可能只会让您满意更困惑了。它非常理论化，所以如果您不能立即理解它，请不要担心。

To understand what O(log(n)) means you might wanna read up on Big O notaion. In shot it means, that if your data set gets 1024 times bigger you runtime will only be 10 times longer (or less)(for base 2).

MergeSort runs in O(n*log(n)), which means it will take 10 240 times longer. Bubble sort runs in O(n^2), which means it will take 1024^2 = 1 048 576 times longer. So there are really some time to safe :)

To understand your sum, you must look at the mergesort algorithm as a tree:

         sort(3,1,2,4)
        /            \
   sort(3,1)      sort(2,4)
    /     \        /     \
sort(3) sort(1) sort(2) sort(4)

The sum iterates over each level of the tree. k=0 it the top, k= log(n) is the buttom. The tree will always be of height log2(n) (as it a balanced binary tree).

To do a little math:

Σ 2^k * 2(n/2^k) = 
2 * Σ 2^k * (n/2^k) =
2 * Σ n*2^k/2^k = 
2 * Σ n = 
2 * n * (1+log(n)) //As there are log(n)+1 steps from 0 to log(n) inclusive

This is of course a lot of work to do, especially if you have more complex algoritms. In those situations you get really happy for the Master Theorem, but for the moment it might just get you more confused. It's very theoretical so don't worry if you don't understand it right away.

回复收藏 0 原文