Версия для сортировки анаграмм и версия для подсчета символов

Question

Я узнаю о сложности времени и теоретически прочитал, что для проверки анаграммы на наличие двух строк одинаковой длины может быть две версии:

1. Сортировка строки и сравнение O (nlogn)
2. Подсчет символов O (n)

, но я хотел продолжить и испытать то же самое, используя код.

Итак, я написал дваверсия кода и проверка времени с использованием модуля Python Timeit, но там я получаю разные результаты.

import timeit


def method_one(input1, input2):
    """
    Check if two string are anagram 
    """

    if len(input1) == len(input2):
        if sorted(input1) == sorted(input2):
            return True
    return False

def method_two(input1, input2):
    """
    Check if two string are anagram using count the character method
    """
    count_char = [0] * 26

    if len(input1) == len(input2):
        for i in range(0, len(input1)):
            count_char[ord(input1[i])-ord("a")] += 1
            count_char[ord(input2[i])-ord("a")] -= 1

        for i in count_char:
            if(bool(i)):
                return False
        return True
    return False

timer1 = timeit.Timer("method_one('apple','pleap')", "from __main__ import method_one")
timer2 = timeit.Timer("method_two('apple','pleap')", "from __main__ import method_two")

print(timer1.timeit(number=10000))
print(timer2.timeit(number=10000))

method_one: 0.0203204
method_two: 0.1090699

В идеале подсчет символов должен быть выигрышным, но результаты противоположны моим ожиданиям.

Answer 1

Временная сложность описывает, как масштабируется время выполнения алгоритма при увеличении входных данных для указанного алгоритма. Поскольку он игнорирует константы, алгоритм, который имеет лучшую временную сложность, не гарантирует, что он будет работать быстрее, чем другие с более высокими границами.

Что говорит вам временная сложность, так это то, что если размер ввода приближается к бесконечности, то наиболее эффективный алгоритм будет работать быстрее.