Что O (log n) означает точно?
Если функция создает объект PyQt, который приложение должно продолжать использовать, вам нужно будет убедиться, что ссылка на него хранится как-то. В противном случае он может быть удален сборщиком мусора Python сразу после возвращения функции.
Таким образом, либо дать объекту родительский объект, либо сохранить его как атрибут какого-либо другого объекта. (В принципе, объект также можно было бы сделать глобальной переменной, но это обычно считается плохой практикой).
Вот пересмотренная версия сценария вашего примера, демонстрирующая, как исправить вашу проблему:
from PySide import QtGui, QtCore
class Window(QtGui.QMainWindow):
def __init__(self):
QtGui.QMainWindow.__init__(self)
menu = self.menuBar().addMenu(self.tr('View'))
action = menu.addAction(self.tr('New Window'))
action.triggered.connect(self.handleNewWindow)
def handleNewWindow(self):
window = QtGui.QMainWindow(self)
window.setAttribute(QtCore.Qt.WA_DeleteOnClose)
window.setWindowTitle(self.tr('New Window'))
window.show()
# or, alternatively
# self.window = QtGui.QMainWindow()
# self.window.setWindowTitle(self.tr('New Window'))
# self.window.show()
if __name__ == '__main__':
import sys
app = QtGui.QApplication(sys.argv)
window = Window()
window.resize(300, 300)
window.show()
sys.exit(app.exec_())
16 ответов
Я не могу понять, как идентифицировать функцию по времени журнала.
Наиболее распространенными атрибутами логарифмической функции времени выполнения являются следующие:
- выбор следующего элемента, над которым будет выполняться какое-либо действие, является одной из нескольких возможностей, а
- нужно будет выбрать только один.
или
- элементы, над которыми выполняется действие, представляют собой цифры n
Вот почему, например, поиск людей в телефонной книге - это O (log n). Вам не нужно проверять каждого человека в телефонной книге, чтобы найти нужного; вместо этого вы можете просто разделять и властвовать, глядя на то, где их имена расположены в алфавитном порядке, и в каждом разделе вам нужно только изучить подмножество каждого раздела, прежде чем вы в конечном итоге найдете чей-то номер телефона.
Конечно, большая телефонная книга все равно займет больше времени, но она не будет расти так быстро, как пропорциональное увеличение дополнительного размера.
Мы можем расширить пример телефонной книги, чтобы сравнить другие виды операций и их время выполнения. Предположим, что в нашей телефонной книге есть предприятий («Желтые страницы») с уникальными именами и людей («Белые страницы»), которые могут не иметь уникальных имен. Номер телефона назначается не более чем одному человеку или компании. Мы также предположим, что для перехода на определенную страницу требуется постоянное время.
Вот время выполнения некоторых операций, которые мы можем выполнять с телефонной книгой, от лучшего к худшему:
O (1) (лучший случай): Учитывая страницу, на которой указано название компании, и название компании, найдите номер телефона.
O (1) (средний регистр): Учитывая страницу, на которой находится имя человека и его имя, найдите номер телефона.
O (log n): Зная имя человека, найдите номер телефона, выбрав случайное место примерно в середине той части книги, которую вы еще не искали, а затем проверьте, является ли имя человека в таком случае. Затем повторите процесс примерно в середине той части книги, где написано имя человека. (Это бинарный поиск по имени человека.)
O (n): Найдите всех людей, в телефонных номерах которых есть цифра «5».
O (n): По номеру телефона найдите человека или компанию с этим номером.
O (n log n): Произошла путаница в офисе типографии, и все страницы нашей телефонной книги были вставлены в случайном порядке. Исправьте порядок, чтобы он был правильным, просматривая имя на каждой странице, а затем помещая эту страницу в соответствующее место в новой пустой телефонной книге.
Для приведенных ниже примеров мы сейчас находимся в офисе типографии. Телефонные книги ждут отправки по почте каждому жителю или компании, и на каждой телефонной книге есть наклейка, указывающая, куда ее следует отправить. У каждого человека или компании есть одна телефонная книга.
O (n log n): Мы хотим персонализировать телефонную книгу, поэтому мы собираемся найти имя каждого человека или компании в их назначенной копии, затем обвести их имя в книге и написать короткое спасибо - Обратите внимание на их покровительство.
O (n 2 ): В офисе произошла ошибка, и каждая запись в каждой телефонной книге имеет дополнительный «0» в конце телефонного номера. Возьмите немного белого цвета и удалите каждый ноль.
O (n · n!): Мы готовы загрузить телефонные книги на транспортную док-станцию. К сожалению, робот, который должен был загружать книги, вышел из строя: он загружает книги в грузовик в случайном порядке! Хуже того, он загружает все книги в грузовик, затем проверяет, находятся ли они в правильном порядке, а если нет, выгружает их и начинает заново. (Это ужасная фиктивная сортировка .)
O (n n ): Вы исправляете робота так, чтобы он загружал вещи правильно. На следующий день один из ваших коллег.Рабочие подшучивают над вами и подключают робота к автоматизированной системе печати. Каждый раз, когда робот загружает оригинальную книгу, заводской принтер выполняет дублирование всех телефонных книг! К счастью, системы обнаружения ошибок робота достаточно сложны, чтобы робот не пытался распечатать еще больше копий, когда встречает дублирующую книгу для загрузки, но ему все равно приходится загружать каждую напечатанную оригинальную и дублирующую книгу.
Чтобы получить более подробное математическое объяснение, вы можете проверить, как временная сложность достигает log n здесь. https://hackernoon.com/what-does-the-time-complexity-o-log-n-actually-mean-45f94bb5bfbf
Логарифмическое время работы ( O (log n) ) по существу означает, что время работы растет пропорционально логарифму входного размера - в качестве примера, если 10 предметы занимает максимум некоторое время x , а 100 предметы занимает максимум 2x , и 10 000 предметы занимает максимум 4x , то это выглядит как O (log n) сложность времени.
Это просто означает, что время, необходимое для выполнения этой задачи, увеличивается с регистрация (n) (пример: 2s для n = 10, 4s для n = 100,...). Дополнительные сведения см. в статьях Википедии на страницах Двоичный алгоритм поиска и Биг О Нотация .
-121--1744365-Полный двоичный пример - O (ln n), потому что поиск выглядит следующим образом:
1 2 3 4 5 6 7 8 9 10 11 12
Поиск 4 дает 3 попадания: 6, 3, а затем 4. И log2 12 = 3, что является хорошим приблизительным к тому, сколько попаданий там, где необходимо.
O (log n) немного вводит в заблуждение, точнее, это O (log 2 n), то есть (логарифм с основанием 2).
Высота сбалансированного двоичного дерева равна O (log 2 n), поскольку каждый узел имеет два (обратите внимание на «два», как в log 2 n) дочерних узла. Итак, дерево с n узлами имеет высоту log 2 n.
Другой пример - двоичный поиск, время выполнения которого равно O (log 2 n), потому что на каждом шаге вы делите пространство поиска на 2.
O(log n) означает, что функция (или алгоритм, или шаг в алгоритме) работает за время, пропорциональное логарифму (обычно основание 2 в большинстве случаев, но не всегда, и в любом случае это несущественно в нотации big-O*) размера входных данных.
Логарифмическая функция является обратной по отношению к экспоненциальной функции. Другими словами, если ваш вход растет экспоненциально (а не линейно, как вы обычно считаете), то ваша функция растет линейно.
Время работы O(log n) очень часто встречается в любом приложении типа "разделяй и властвуй", потому что (в идеале) каждый раз вы сокращаете работу вдвое. Если на каждом из шагов разделения или покорения вы выполняете работу с постоянным временем (или работу, которая не является постоянной по времени, но время которой растет медленнее, чем O(log n)), то вся ваша функция будет O(log n). Довольно часто каждый шаг требует линейного времени на входе; в этом случае общая временная сложность составит O(n log n).
Временная сложность двоичного поиска является примером O(log n). Это связано с тем, что при двоичном поиске вы всегда игнорируете половину входных данных на каждом последующем шаге, разделяя массив пополам и фокусируясь только на одной половине на каждом шаге. Каждый шаг занимает постоянное время, потому что при двоичном поиске вам нужно сравнить только один элемент с вашим ключом, чтобы понять, что делать дальше, независимо от того, насколько велик рассматриваемый вами массив в любой момент времени. Таким образом, вы делаете примерно log(n)/log(2) шагов.
Временная сложность сортировки слиянием является примером O(n log n). Это связано с тем, что на каждом шаге вы делите массив пополам, в результате чего общее количество шагов составляет приблизительно log(n)/log(2). Однако на каждом шаге вам нужно выполнить операции слияния для всех элементов (будет ли это одна операция слияния для двух подсписков из n/2 элементов или две операции слияния для четырех подсписков из n/4 элементов, не имеет значения, поскольку это добавляет необходимость делать это для n элементов на каждом шаге). Таким образом, общая сложность составляет O(n log n).
* Помните, что в нотации big-O, по определению, константы не имеют значения. Также по правилу смены основания для логарифмов, единственное различие между логарифмами с разными основаниями - это постоянный коэффициент.
O(log N) в основном означает, что время увеличивается линейно, а n увеличивается экспоненциально. Так, если для вычисления 1 секунды требуется 10 элементов, то для вычисления 100 элементов потребуется 2 секунды, 3 секунды для вычисления 1000 элементов и так далее.
Это O(log n), когда мы используем алгоритмы типа "разделяй и властвуй", например, двоичный поиск. Другой пример - быстрая сортировка, когда каждый раз мы делим массив на две части, и каждый раз требуется O(N) времени, чтобы найти поворотный элемент. Следовательно, N O(log N)
Вы можете думать об O (log N) интуитивно, говоря, что время пропорционально количеству цифр в N.
Если операция выполняет работу с постоянным временем для каждой цифры или бита ввода, вся операция займет время, пропорциональное количеству цифр или битов на входе, а не величине ввода; таким образом, O (log N), а не O (N).
Если операция принимает серию решений с постоянным временем, каждое из которых уменьшает вдвое (уменьшает в 3, 4, 5 ...) размер входных данных, которые необходимо учитывать, для всего потребуется время, пропорциональное логарифмической базе 2. (основание 3, основание 4, основание 5 ...) размера N ввода, а не O (N).
И так далее.
Но что именно означает O(log n)
Что это означает, так это "по мере того, как n стремится к бесконечности, время стремится к a*log(n), где a - постоянный масштабный коэффициент".
Или, на самом деле, это не совсем так; скорее всего, это означает что-то вроде "time деленное на a*log(n) стремится к 1".
"Стремится" имеет обычное математическое значение из "анализа": например, что "если выбрать любую произвольно малую ненулевую константу k, то я смогу найти соответствующее значение X такое, что ((time/(a*log(n))) - 1) меньше k для всех значений n больше X. "
В простых терминах это означает, что уравнение для времени может иметь некоторые другие компоненты: например, оно может иметь некоторое постоянное время запуска; но эти другие компоненты бледнеют до незначительности при больших значениях n, и a*log(n) является доминирующим членом при больших n.
Заметим, что если бы уравнение было, например, ...
time(n) = a + blog(n) + cn + dnn
... то это было бы O(n квадрат), потому что, независимо от значений констант a, b, c и ненулевого d, член d*n*n всегда доминирует над остальными для любого достаточно большого значения n.
Вот что означает обозначение бит O: оно означает "каков порядок доминирующего члена для любого достаточно большого n".
Если вы построите логарифмическую функцию на графическом калькуляторе или чем-то подобном, вы увидите, что она растет очень медленно - даже медленнее, чем линейная функция.
Вот почему алгоритмы с логарифмической временной сложностью пользуются большим спросом: даже для действительно больших n (скажем, n = 10 ^ 8, например) они работают более чем приемлемо.
Если бы у вас была функция, которая принимает:
1 millisecond to complete if you have 2 elements.
2 milliseconds to complete if you have 4 elements.
3 milliseconds to complete if you have 8 elements.
4 milliseconds to complete if you have 16 elements.
...
n milliseconds to complete if you have 2**n elements.
Тогда она принимает log 2 (n) раз. Нотация Big O , грубо говоря, означает, что соотношение должно быть истинным только для больших n, и что постоянные множители и меньшие члены можно игнорировать.
Проще говоря: на каждом шаге вашего алгоритма вы можете сократить работу вдвое. (Асимптотически эквивалентно третьему, четвертому, ...)
Лучший способ, который я всегда использовал для мысленного представления алгоритма, работающего за O(log n), следующий:
Если вы увеличиваете размер задачи на мультипликативную величину (т.е. умножаете ее размер на 10), работа увеличивается только на аддитивную величину.
Применим это к вопросу о двоичном дереве, чтобы у вас было хорошее приложение: если вы удвоите количество узлов в двоичном дереве, высота увеличится только на 1 (аддитивная величина). Если вы удвоите его еще раз, оно все равно увеличится только на 1. (Очевидно, я предполагаю, что оно остается сбалансированным и т.д.). Таким образом, вместо того, чтобы удваивать работу при увеличении размера задачи, вы делаете лишь очень небольшое увеличение работы. Вот почему алгоритмы O(log n) являются потрясающими.
Логарифмическое время выполнения ( O (log n) ) по существу означает, что время выполнения растет пропорционально логарифму входного размера - например, если 10 элементов занимают самое большее некоторое количество времени x , а 100 элементов занимают самое большее, скажем, 2x , а 10 000 элементов занимают самое большее 4x , тогда это выглядит как временная сложность O (log n) .
На этот вопрос уже было опубликовано много хороших ответов, но я считаю, что нам действительно не хватает важного, а именно, иллюстрированного ответа.
Что значит сказать, что высота полного двоичного дерева равна O (log n)?
На следующем рисунке изображено двоичное дерево. Обратите внимание, что каждый уровень содержит удвоенное количество узлов по сравнению с уровнем выше (отсюда двоичный ):
Двоичный поиск - это пример со сложностью O (log n) . Предположим, что узлы нижнего уровня дерева на рисунке 1 представляют элементы в некоторой отсортированной коллекции. Двоичный поиск - это алгоритм «разделяй и властвуй», и на рисунке показано, как нам потребуется (максимум) 4 сравнения, чтобы найти запись, которую мы ищем в этом наборе данных из 16 элементов.
Предположим, вместо этого у нас есть набор данных из 32 элементов. Продолжая рисовать выше, мы обнаружим, что теперь нам понадобятся 5 сравнений, чтобы найти то, что мы ищем, поскольку дерево выросло только на один уровень глубже, когда мы умножили количество данных. В результате сложность алгоритма можно описать как логарифмический порядок.
Нанесение log (n) на простой лист бумаги приведет к графику, на котором подъем кривой замедляется по мере увеличения n :
Алгоритмы разделения и владения обычно имеют компонент logn времени выполнения. Это происходит из-за многократного уменьшения вдвое входных данных.
В случае бинарного поиска на каждой итерации вы выбрасываете половину ввода. Следует отметить, что в нотации Big-O журнал - это лог-база 2.
Редактировать: Как уже отмечалось, база журнала не имеет значения, но при вычислении производительности алгоритма Big-O будет учитываться коэффициент журнала. от деления вдвое, поэтому я считаю его основанием 2.
Это просто означает, что время, необходимое для этой задачи, увеличивается с log (n) (пример: 2 секунды для n = 10, 4 секунды для n = 100, ...). Прочтите статьи Википедии о алгоритме двоичного поиска и нотации Big O для большей точности.
Что такое logb(n)?
Это количество раз, которое можно многократно разрезать бревно длины n на b равных частей до получения отрезка размером 1.