你如何分析这个排序算法的时间复杂度？

Question

TL;DR - 一种非比较排序算法，其执行时间根据数据类型中的位数进行缩放；您如何正确评估 Big O 时间复杂度？

我有一个排序算法“Bitsort”，它的时间复杂度取决于要排序的数据类型中的位数，而不是要排序的列表的长度；对于长度从 2 个元素到最大可寻址大小的列表，完全排序所需的遍历整个列表的次数由列表中使用的数据类型的大小决定。 bitsort 的简单版本（下面未优化但有效的代码示例）一次对列表排序 1 位。在现实世界中，这通常意味着 32 位系统在数据类型和要排序的列表的最大长度方面都有 32 位；和 2^32 的 Log-base2 是 32。因此，可以说简单的位排序的时间复杂度从 O(NB) 到 O(NLogN)，其中 B 是位数，因为 N 达到最大长度数组系统可以处理。但是，从绝对意义上讲，随着 N 趋于无穷大，B 保持不变，因此可以说时间复杂度为 O(N)。

对于简单的位排序，应该如何评估时间复杂度？

import sys
from random import randrange

def checkOrder(arr):
    for i in range(1, len(arr)):
        if arr[i - 1] > arr[i]:
            return False
    return True


def randomArray(length, height):
    result = []
    for i in range(0, length):
        result.append(randrange(0, height, 1))
    return result


def swap(arr, left, right):
    temp = arr[left]
    arr[left] = arr[right]
    arr[right] = temp
    

# pat. pending, but not a troll
def bitsort(arr, begin, end, shiftBit):
    if end-begin <= 0 or shiftBit < 0:
        return
    LP, RP = begin - 1, end + 1
    mask = 0b1 << shiftBit

    while True:
        LP += 1
        if LP > end:
            bitsort(arr, begin, end, shiftBit - 1)
            return
        elif LP == RP:
            if LP <= begin: # left has 0 or 1 el
                pass
            else: 
                bitsort(arr, begin, LP - 1, shiftBit - 1)
            if RP >= end: # right has 0 or 1 elements
                pass
            else: 
                bitsort(arr, RP, end, shiftBit - 1) 
            return
        if arr[LP] & mask == 0:
            continue
        else:
            while True:
                RP -= 1
                if RP < begin:
                    bitsort(arr, begin, end, shiftBit - 1)
                    return
                elif LP == RP:
                    if LP <= begin:  
                        if RP <= end:
                            bitsort(arr, begin, end, shiftBit - 1)
                            return
                        else:
                            pass
                    else:  
                        bitsort(arr, begin, LP - 1, shiftBit - 1) 
                    if RP >= end:  
                        pass
                    else:  
                        bitsort(arr, RP, end, shiftBit - 1) 
                    return
                if (arr[RP] & mask) >> shiftBit == 1:
                    continue
                else:
                    swap(arr, LP, RP)
                    break


def main(args):
    arr = randomArray(1000000, 2147483648)
    bitsort(arr, 0, len(arr) - 1, 31)
    print(f'Proper order: {checkOrder(arr)}')


if __name__ == '__main__':
    main(sys.argv[1:])

Answer 1

我相信您的分析是正确的，并且作为 N 和 B 的函数，完成的工作是 O(NB)，然后关注您的问题，即如何将其与，比方说, O(N log N).

分析此类排序算法时的典型惯例是 - 至少从 CS 理论的角度来看 - 将其分类为 O(NB) 而不是 O(N log N) 或 O(N)。以下是几个原因：

想象一下，您正在对一个数字列表进行排序，您知道这些数字中没有多少位（例如，可能是美国 phone 区号或美国邮政编码，它们是最多十位长）。在这种情况下，您可以将算法调整为仅处理每个数字的前十位，从而减少对所有内容进行排序所需的遍数。 O(NB) 的运行时间更清楚地表明了这一点，因为 B 相应地减少了运行时间。
虽然我们目前使用的机器的字长通常为 32 或 64，但原则上我们可以根据需要将字长调大。例如，SIMD 指令允许对比这更多的位进行并行操作。或者您可能正在对可变长度整数进行排序，就像您可能对 RSA 密钥所做的那样。在那种情况下，我们不一定声称运行时间是 O(N log N)，因为我们不能保证 B = O(log N)。在后一种情况下说运行时间为 O(N) 也是不正确的，因为我们不能假装 B 是一个常数。
显式写出 O(NB) 允许我们将此排序算法与其他整数排序算法进行比较。例如，我们有运行时间为 O(N log B) 和 O(N log N / log B) 的排序算法。保留 B 项可以更轻松地了解这些其他算法与您的算法的比较。
对于大 B 和小得多的 N，O(N log N) 的运行时间是不正确的。在这种情况下，您可能会做比 O(log N) 轮更多的位排序例程.

你如何分析这个排序算法的时间复杂度？

How Do You Analyze This Sorting Algorithm's Time Complexity?

sorting

big-o