Как оценить вложенные логические значения? - PullRequest
Новая
       24

Как оценить вложенные логические значения?

0 голосов
/ 28 февраля 2019

Я относительно новичок в python и освоился с основами, даже для циклов, например.Я столкнулся с функцией ниже, и когда я попытался понять, что она делает, я был сбит с толку.Он всегда возвращает список, который был передан через функцию, и, по-видимому, присваивает логическому значению False элемент «x» на основе длины переданного списка, в конечном итоге разрывая цикл, когда значения false недело.Что я не понимаю, так это роль первого элемента в цикле for относительно второго цикла for (он вычитается из размера).Если бы кто-нибудь мог помочь мне лучше понять, что делает эта функция, это было бы оценено. 

def myfunc(list):

    size = len(list)

    for x in range(0, size):
        foo = False

        for x2 in range(0, size - x - 1):
            if list[x2] > list[x2 + 1]:
                list[x2], list[x2 + 1] = list[x2 + 1], list[x2]
                foo = True

        if not foo: break

    return list

1 Ответ

0 голосов
/ 28 февраля 2019

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

Хотя вам не обязательно останавливать второй цикл for на size - x - 1 итерациях, это помогает уменьшить количество выполняемых сравнений, повышая тем самым эффективность алгоритма, уже имеющего временную сложность порядкаиз п ^ 2, который плохо работает в больших списках.

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

Таким образом, ваша программа рано останавливает внутренний цикл, зная, что последние элементы x уже отсортированы.

Когда дело доходит до логического значения, оно еще больше уменьшает сравнение, которое вы выполняете.Например, когда вы передаете отсортированный список: На первой итерации внешнего цикла, x = 0.Затем внутренний цикл выполняет итерацию size - 1 раз, сравнивая соседние элементы, но не выполняет обмен, так как элементы уже в порядке.Как только внутренний цикл завершает все итерации для первой итерации внешнего цикла (x = 0), бессмысленно идти на дальнейшие итерации и лучше останавливать алгоритм в этой точке.Оператор break гарантирует, что это произойдет.

Таким образом, в лучшем случае временная сложность вашего алгоритма будет порядка n (O(n)), что лучше, чем средняя или наихудшая сложность O(n^2)

...