diff options
author | Philip Withnall <philip@tecnocode.co.uk> | 2020-09-02 13:09:52 +0000 |
---|---|---|
committer | Philip Withnall <philip@tecnocode.co.uk> | 2020-09-02 13:09:52 +0000 |
commit | eba91d5c871108ea057e0cd92db552b472517c9e (patch) | |
tree | 3da7070d07aae1ff129d0df11303edde471d1f7a | |
parent | b01bcd38a6bfd3c02f76b2b44efc939bcc1b5ada (diff) | |
parent | d27549b0f42b319a22593a957d38a90f101aa899 (diff) | |
download | glib-eba91d5c871108ea057e0cd92db552b472517c9e.tar.gz |
Merge branch 'big_O_notations' into 'master'
Big o notations
See merge request GNOME/glib!1025
-rw-r--r-- | glib/garray.c | 12 | ||||
-rw-r--r-- | glib/ghash.c | 7 | ||||
-rw-r--r-- | glib/glist.c | 7 | ||||
-rw-r--r-- | glib/gqueue.c | 3 | ||||
-rw-r--r-- | glib/gsequence.c | 5 | ||||
-rw-r--r-- | glib/gslist.c | 7 | ||||
-rw-r--r-- | glib/gtree.c | 19 |
7 files changed, 45 insertions, 15 deletions
diff --git a/glib/garray.c b/glib/garray.c index 4d29bc068..3f23b980d 100644 --- a/glib/garray.c +++ b/glib/garray.c @@ -58,17 +58,21 @@ * * To create a new array use g_array_new(). * - * To add elements to an array, use g_array_append_val(), - * g_array_append_vals(), g_array_prepend_val(), g_array_prepend_vals(), - * g_array_insert_val() and g_array_insert_vals(). + * To add elements to an array with a cost of O(n) at worst, use + * g_array_append_val(), g_array_append_vals(), g_array_prepend_val(), + * g_array_prepend_vals(), g_array_insert_val() and g_array_insert_vals(). * - * To access an element of an array (to read it or write it), + * To access an element of an array in O(1) (to read it or to write it), * use g_array_index(). * * To set the size of an array, use g_array_set_size(). * * To free an array, use g_array_unref() or g_array_free(). * + * All the sort functions are internally calling a quick-sort (or similar) + * function with an average cost of O(n log(n)) and a worst case + * cost of O(n^2). + * * Here is an example that stores integers in a #GArray: * |[<!-- language="C" --> * GArray *garray; diff --git a/glib/ghash.c b/glib/ghash.c index 4fe2912fb..40a0fb2ca 100644 --- a/glib/ghash.c +++ b/glib/ghash.c @@ -68,13 +68,14 @@ * given a key the value can be found quickly * * A #GHashTable provides associations between keys and values which is - * optimized so that given a key, the associated value can be found - * very quickly. + * optimized so that given a key, the associated value can be found, + * inserted or removed in amortized O(1). All operations going through + * each element take O(n) time (list all keys/values, table resize, etc.). * * Note that neither keys nor values are copied when inserted into the * #GHashTable, so they must exist for the lifetime of the #GHashTable. * This means that the use of static strings is OK, but temporary - * strings (i.e. those created in buffers and those returned by GTK+ + * strings (i.e. those created in buffers and those returned by GTK * widgets) should be copied with g_strdup() before being inserted. * * If keys or values are dynamically allocated, you must be careful to diff --git a/glib/glist.c b/glib/glist.c index 474331ab5..68673768d 100644 --- a/glib/glist.c +++ b/glib/glist.c @@ -40,7 +40,12 @@ * @short_description: linked lists that can be iterated over in both directions * * The #GList structure and its associated functions provide a standard - * doubly-linked list data structure. + * doubly-linked list data structure. The benefit of this data-structure + * is to provide insertion/deletion operations in O(1) complexity where + * access/search operations are in O(n). The benefit of #GList over + * #GSList (singly linked list) is that the worst case on access/search + * operations is divided by two which comes at a cost in space as we need + * to retain two pointers in place of one. * * Each element in the list contains a piece of data, together with * pointers which link to the previous and next elements in the list. diff --git a/glib/gqueue.c b/glib/gqueue.c index 0cc7ab200..f7acb945a 100644 --- a/glib/gqueue.c +++ b/glib/gqueue.c @@ -29,7 +29,8 @@ * * The #GQueue structure and its associated functions provide a standard * queue data structure. Internally, GQueue uses the same data structure - * as #GList to store elements. + * as #GList to store elements with the same complexity over + * insertion/deletion (O(1)) and access/search (O(n)) operations. * * The data contained in each element can be either integer values, by * using one of the [Type Conversion Macros][glib-Type-Conversion-Macros], diff --git a/glib/gsequence.c b/glib/gsequence.c index c0fa9d6c9..96f21d6e4 100644 --- a/glib/gsequence.c +++ b/glib/gsequence.c @@ -30,7 +30,10 @@ * * The #GSequence data structure has the API of a list, but is * implemented internally with a balanced binary tree. This means that - * it is possible to maintain a sorted list of n elements in time O(n log n). + * most of the operations (access, search, insertion, deletion, ...) on + * #GSequence are O(log(n)) in average and O(n) in worst case for time + * complexity. But, note that maintaining a balanced sorted list of n + * elements is done in time O(n log(n)). * The data contained in each element can be either integer values, by using * of the [Type Conversion Macros][glib-Type-Conversion-Macros], or simply * pointers to any type of data. diff --git a/glib/gslist.c b/glib/gslist.c index 15b7936c6..c0df55ff5 100644 --- a/glib/gslist.c +++ b/glib/gslist.c @@ -39,7 +39,12 @@ * @short_description: linked lists that can be iterated in one direction * * The #GSList structure and its associated functions provide a - * standard singly-linked list data structure. + * standard singly-linked list data structure. The benefit of this + * data-structure is to provide insertion/deletion operations in O(1) + * complexity where access/search operations are in O(n). The benefit + * of #GSList over #GList (doubly linked list) is that they are lighter + * in space as they only need to retain one pointer but it double the + * cost of the worst case access/search operations. * * Each element in the list contains a piece of data, together with a * pointer which links to the next element in the list. Using this diff --git a/glib/gtree.c b/glib/gtree.c index e8d4e204c..41f2438f1 100644 --- a/glib/gtree.c +++ b/glib/gtree.c @@ -42,11 +42,17 @@ * * The #GTree structure and its associated functions provide a sorted * collection of key/value pairs optimized for searching and traversing - * in order. + * in order. This means that most of the operations (access, search, + * insertion, deletion, ...) on #GTree are O(log(n)) in average and O(n) + * in worst case for time complexity. But, note that maintaining a + * balanced sorted #GTree of n elements is done in time O(n log(n)). * * To create a new #GTree use g_tree_new(). * - * To insert a key/value pair into a #GTree use g_tree_insert(). + * To insert a key/value pair into a #GTree use g_tree_insert() + * (O(n log(n))). + * + * To remove a key/value pair use g_tree_remove() (O(n log(n))). * * To look up the value corresponding to a given key, use * g_tree_lookup() and g_tree_lookup_extended(). @@ -57,8 +63,6 @@ * To traverse a #GTree, calling a function for each node visited in * the traversal, use g_tree_foreach(). * - * To remove a key/value pair use g_tree_remove(). - * * To destroy a #GTree, use g_tree_destroy(). **/ @@ -380,6 +384,9 @@ g_tree_destroy (GTree *tree) * * The tree is automatically 'balanced' as new key/value pairs are added, * so that the distance from the root to every leaf is as small as possible. + * The cost of maintaining a balanced tree while inserting new key/value + * result in a O(n log(n)) operation where most of the other operations + * are O(log(n)). */ void g_tree_insert (GTree *tree, @@ -567,6 +574,10 @@ g_tree_insert_internal (GTree *tree, * make sure that any dynamically allocated values are freed yourself. * If the key does not exist in the #GTree, the function does nothing. * + * The cost of maintaining a balanced tree while removing a key/value + * result in a O(n log(n)) operation where most of the other operations + * are O(log(n)). + * * Returns: %TRUE if the key was found (prior to 2.8, this function * returned nothing) */ |