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

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

  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

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


person Honey Kumar    schedule 03.07.2019    source источник


Ответы (1)


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

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

person hbejgel    schedule 05.07.2019