При анализе временной сложности сортировки слияния я знаю, что, поскольку есть уровни O (log (n)), и каждый уровень принимает операцию O (n), вся временная сложность должна быть O (nlog (n)) ,сложность слияния O (nlogn) + O (n)?
Однако, не делясь взять O (n) всего? Каждое деление множества элементов принимает O (1), но вы делите общее количество O (n), так что разделительная часть сортировки слияния не принимает O (n)? Например, если у вас есть 8 элементов, вам нужно разделить 7 раз, и если у вас есть 16 элементов, вам нужно разделить 15 раз.
Итак, не следует ли, чтобы вся процедура определения времени слияния технически была O (nlog (n)) + O (n)? Я знаю, что O (nlog (n) + n) - это то же самое, что и O (nlog (n)), но никто не упоминает об этом в объяснении сложности времени сортировки слияния.
Вы знаете, что они такие же, но не понимают, почему никто так не говорит? –
Я просто думаю, что моя логика процесса удаления, являющаяся O (n), может быть ошибочной, поскольку я не вижу нигде в том, что часть удаления является O (n), но в конечном счете игнорируется в конце. – David
Это не то, что вы просили; вы спросили, почему O (n) -терминал был проигнорирован для алгоритма O (n log n), и по той же причине любой sub-O (n log n) (например, O (1)) игнорируется, так как другие объяснил, и вы утверждаете, что уже понимаете. –