Beh*_*ooz 1 sorting algorithm complexity-theory
维基百科没有任何关于它的内容.
谁知道呢？
我只想知道该算法的平均Big-O复杂度.
的？http://www.freeimagehosting.net/uploads/f18f22a095.jpg
gnome的排序算法的性能是至少O(f(n))其中f(n)为在至该元件应该结束了的距离的输入列表中的每个元素的总和.对于长度的"随机"列表,列表L开头的元素预期是L / 2远离其排序位置的平均距离.列表中间的元素应该是L / 4距离其排序位置的平均距离.由于存在L总元素,f(n)至少是L * L / 4.因此,平均而言,gnome排序是O(n * n).
对不起,如果这很难理解.
