Post pobrano z: Veintidos Grados

Post pobrano z: Ditalia

Post pobrano z: Das Bevo

Post pobrano z: The Document Outline Dilemma

For the past few weeks there has been lots of talk about HTML headings in web standards circles. Perhaps you’ve seen some of the blog posts, tweets, and GitHub issue threads. Headings have been part of HTML since the very first websites at CERN, so it might be surprising to find them controversial 25 years later. I’m going to quickly summarize why they are still worth discussing, with plenty of links to other sources, before adding my own opinions to the mix. If you’re up-to-date on the debate, you can jump straight to the „Bigger Dilemma” section.

The Story So Far…

HTML uses headings (<h1>, <h2>, <h3>, and so on until <h6>) to mark up titles for a subsequent section of text. The numbers (or levels) of the heading elements are supposed to logically correspond to a tree-like structure of nested sections, like books that have chapters with sections and sub-sections.

However, HTML markup did not originally have a way to reflect this nested logical structure in a nested DOM structure. Unlike nested lists, nested headings weren’t actually nested in elements that defined the parent sections. Heading elements of different levels were all sibling elements, and also siblings to the paragraphs they provide a title for. The „sections” were a purely logical structure, not a DOM structure, containing all markup that starts with a heading and continued until you reached another heading of the same or higher level.

As Brian Kardell points out, this made perfect sense in the „flat earth markup” of early HTML, where tags were just typographic instructions inserted into a flow of text. The concept of an HTML page as a tree structure came later, when so-called Dynamic HTML needed a document object model (DOM) to describe that flow of text and tags as a data structure that scripts could access.

Not to spoil the ending, but HTML now has a <section> element which can (optionally) be used to create a nested DOM structure to match your logical heading structure. The <main>, <header>, <footer>, <article>, <aside>, and <nav> elements all also help create a nested document structure that is reflected in DOM nesting.

But there was another problem with the originally heading model: it couldn’t easily be remixed in template systems. Because the heading level is expressed by the tag name (<h1> versus <h4>), rather than by the context in which it’s used, you can’t easily re-use the same content in a different context where the level would be different. For example, a blog might use the same set of article headlines and intro paragraphs in many contexts: as stand-alone blog post pages; as abstracts on a main index page; or as abstracts on an archive page which also has headings dividing the list by month or year. What heading level should the article title be?

Early proposals for sectioning elements also included a level-free <h> or <heading> element, that would be assigned a level based on context. (In fact, the idea goes back to the earliest discussions of HTML.) But when sectioning elements were finally added to HTML, they were designed to work with the existing heading elements. However, the specifications defined a „Document Outline Algorithm” which would re-calculate the heading levels for the existing numbered heading tags, based on section nesting.

With the Document Outline Algorithm, you could (theoretically) use an <h1> for all headings, and the browser would figure out the level of each heading based on its nesting within <article>, <section>, and related elements. The outline algorithm would ensure that the top heading in the page would be a level 1, and that all other headings would be nested in a consistent order, with no levels skipped. The WHATWG version of the outline also defines rules for dealing with multi-part headings in <hgroup> elements, so the sub-headings do not create sub-sections. (The W3C version of HTML 5 instead declared <hgroup> obsolete: multi-part headings should be marked up as paragraphs inside a section <header> or spans inside the main heading element.)

Browsers modified their default styles so that headings inside of nested sections would have progressively smaller font sizes (just like how the default style for <h3> has smaller font than <h2>, which is smaller than <h1>). But they didn’t change the way they exposed heading levels to the accessibility APIs that are used by screen readers. And screen-reader users are the only ones who really experience heading levels as part of the user interface.

Screen readers announce the numbered level when reading headings, and they allow users to quickly scan through headings of a given level. According to a WebAIM survey, two-thirds of screen-reader users scan headings as the first step of trying to find information on a long web page. For these users, the only effect of the Document Outline Algorithm was that some new pages (eagerly adopting the new spec) were presented as flat lists of level-one headings, with no structure at all.

Why won’t browsers use the outline algorithm for accessible heading levels? Many arguments have been made, but the most compelling one is that it could alter the way existing web sites are presented to screen-reader users, and it’s not clear that those alterations would mostly be positive.

Adrian Roselli has compiled a good overview of the discussions about the problems caused by the unimplemented outline specification, in „There is No Document Outline”. The latest W3C HTML specs only use the document outline algorithm to suggest how authors should synchronize their numbered heading tags with their nested sectioning elements. The WHATWG HTML specs still have the full outline algorithm described as a normative requirement, although there is an open issue where many suggest removing it altogether. As WHATWG spec editor Domenic Denicola puts it:

At some point we cannot claim that user agents are broken. They are instead rejecting our change request.

The Current Debate

The latest flurry of debate was sparked when Jonathan Neal filed an issue on the W3C HTML spec re-proposing the elusive <h> element. The key to the proposal is that an <h> heading element could have a nesting level defined by sectioning elements, while still allowing the existing numbered heading tags to have the level determined by their tag name. Authors would opt in to the outline algorithm by using the new tag. Until browsers supported <h>, a JavaScript (or server-side) polyfill could calculate the heading levels and add them into the DOM with ARIA attributes: role="heading" and aria-level="3" tell the browser to treat an element as a level-3 heading for accessibility purposes, regardless of tag name or nesting, so the page author ends up fully responsible for any heading confusion.

There’s a lot of good discussion on that issue page, and in longer linked blog posts. The main argument in favour of adding a new element is that it wouldn’t change the meaning of existing content. In addition to Neal’s arguments on GitHub, Brian Kardell’s proposal of a custom element and polyfill approaches the issue from this point of view. On the other side, Jake Archibald argues for fixing the elements we already have:

The work needed to fix the existing web is a subset of creating a new element that does the same thing, but doesn’t fix the existing web.

In other words, if the outline algorithm is so great that it’s worth a new element, why not just implement the outline algorithm for existing elements instead?

If you’re still having a hard time understanding why no one can agree about what to do with something as seemingly simple as HTML heading, Brian Kardell has helpfully stripped away all the technical details in a second post.

The Bigger Dilemma

There is a hidden assumption below all the discussion of how to create a document outline for a web page. Discussing how to create the document outline assumes that the structure of a web page can be defined as an outline: as a tree where the nesting level of a heading defines its importance.

I personally don’t think a simple nested outline can capture all the levels of meaning that are conveyed by HTML heading levels, as they are used on the web. I’ll get to why in a bit. But there’s a reason that all the discussion has focused on this type of outline: because this is the type of outline screen readers expect.

For most web users, and web authors, the document outline is irrelevant. They do not know and do not care how the headings and sections are nested, they only see what’s on the screen. And what’s on the screen, in most web pages today, is a two-dimensional layout of content, some of it nested, but some of it independent, with each part given implied importance and relationships by layout, colors, and typography.

So, the question we should be debating isn’t „How should we assign outline levels to headings?” It’s: „How can we summarize the meaningful structure of a web page, so that people using assistive technology can easily find content?”

I’d personally love it if browsers added a feature, for all users, to show the outline as a table of contents, and make it possible to quickly navigate to headings with the keyboard. Maybe if they did, more web authors would pay attention to what their outline looked like. But the browsers don’t, and so most authors don’t.

If you do want to see what your website’s heading outline looks like—and how it would theoretically look like using the document outline algorithm—you can use the W3C Nu HTML validator service, with the Show Outlines option checked.

As it currently stands, the document outline is only of daily importance to screen-reader users, and those users are currently used to dealing with the mess of erratic heading levels in web pages. I’m sure many screen-reader users would appreciate heading levels being fixed. But fixing headings for screen-reader users doesn’t just mean creating a tree of neatly nested headings with no skipped level numbers. It means creating a heading structure that accurately reflects the meaning intended by the creators of the web page, the meaning that visual users infer from style and layout. And in order to do that, we need to consider how meaning is communicated to all the users of web pages who aren’t hearing each heading announced with a numerical level.

A Language is Defined by Those Who Speak It

HTML is unique among computer code languages, because it defines so many constructs without assigning them specific behavior. Meaning in computer code is known as the semantic side of the language, as opposed to the syntactic structures of its grammar. But in most programming languages, the semantic aspects of built-in objects are still strongly tied to instructions for the computer. In JavaScript, new Date() and new Promise() have the same syntax—calling a constructor function—but your JS interpreter understands the semantic distinction between the two object names, and behaves very differently for each.

In contrast, an HTML <article> or a <section> doesn’t come with any instructions for what your web browser should do with it (other than the un-implemented outline algorithm). Instead, the difference between the two is all about the meaning of the content, a way to provide machine-readable annotations for the information communicated from one human being, the website author, to another: the reader.

Meaning in human communication is difficult to define, and never static. But most importantly of all, it is defined by the people who use the language. Dictionaries compile summaries of the meanings that are used, but they don’t restrict them. If people start using words in new and different ways, the dictionary (if it’s any good) will update their definitions.

When I was in grade school, a librarian showed off the multi-volume Oxford English Dictionary by introducing us to a selection of wild and crazy words. Google* was the name for the number that would be written as a 1 followed by 100 zeros (10¹⁰⁰, in scientific notation). Crazy, right? Who would ever need to know a word like that? But times change. In 2006, the OED added a new definition, google as a verb (meaning to use the Google search engine), which might be used a google times more often than the number quantity in modern English conversation.

*Correction: As Mark notes in the comments, the correct spelling of the word I was shown all those years ago is actually googol. And now I don’t know what to believe anymore.

When it comes to the meaning of HTML tags, the equivalent of dictionaries are the two competing HTML specifications (WHATWG and W3C). And just like dictionaries, they both started out as efforts to describe the language as it was currently used.

The fact that there are two different HTML specifications make discussing changes more difficult, but it also strongly highlights the collective, consensus-based nature of HTML as a language. There is no one defining document setting the rules for HTML. HTML is defined by the people who write it and by the web browsers that interpret it.

But it’s not that simple, of course. HTML isn’t only used by human beings, it is also used by computers. And computers aren’t very good about handling fuzzy and shifting meaning.

Whenever you ask a computer to do something with your content—like, for example, tell the screen reader what headings there are in this website and how they are organized—it needs clear and explicit rules for how to do so. If some web authors are using heading tags in one way, and some authors are using the same tags with different meaning, your browser is going to need additional rules to figure out which is which—or else it’s going to get it wrong, at least some of the time.

The driving force of the web standards movement was a hope that all web browsers would react to web page code in (approximately) the same way. And that means defining new features in standards documents before they can be used on the web. Instead of being descriptive, like a dictionary (defining how things are), they are prescriptive, like a legal code (defining how things should be).

The slow pace of developing standards, with lots of input from browser teams, is supposed to ensure that the end result is both prescriptive and descriptive, at least for the parts of the language that describe browser behavior. But it doesn’t always work. There are lots of details in both specs that don’t match actual browser behavior. The W3C’s issue repo even has a comfortingly-named Match Reality Better label aimed at fixing these bits.

And that’s just for the features that describe what browsers should do. What about all the HTML elements that define the semantics of content? Shouldn’t those „match reality better,” too?

A few months ago Sara Soueidan suggested to the W3C HTML working group that maybe the <address> element should be valid for all addresses (and not just page-owner contact addresses). Many people before her have certainly made the same complaint. But this time, something happened. Following a little rough data scraping, which suggested that actual usage in the wild wasn’t restricted to the original definition, the definition in the W3C specs was updated.

Does it make any difference? Maybe not. Browsers don’t do anything with <address> except make it italic. And the WHATWG HTML specs still have the old definition. But it means the spec comes a little closer to describing the way code is actually used on the web, not how someone once imagined it might be.

Which brings us back, at last, to headings: How are they actually used on the web? And is it even possible to define a prescriptive set of instructions, for web authors and for web browsers, that ensure that the meaning of headings can be correctly communicated to screen readers (and potentially, other software)?

The Many Meanings of Headings

What is a heading? It’s a short title for a section of a document. The heading for this section is „The Many Meanings of Headings.” So far, so good.

But all headings are not created equal.

There are big headings:

and there are much smaller headings:

If you inspect the code, you’ll see that one of those is an <h1> and the other is an <h6>. Both of them are wrapped in <figure> tags, which—according to the document outline algorithm—should encapsulate them and keep them from messing up the main document outline. But we all know by now that the document outline algorithm isn’t actually used by web browsers, so apologies to any screen reader users who ended up halfway down the article by mistake.

For anyone reading this article with their eyes in a modern browser, the difference between the two headings is communicated by the font size, and possibly the font style. The exact details will depend on whether you’re looking at the website’s CSS or your browser’s reading mode CSS, and on how recently Chris has changed CSS-Tricks’ styles. But unless Chris has really messed things up, it will be pretty clear to visual readers that the <h1> is bigger and more important than the <h6>. We could change the CSS so they looked identical, but at this point it is hard to understand why you would want to do that. If you wanted them to look the same, why not use the same tag name?

So let’s go a step further, and put those two headings together with some filler text in between. Here’s one way we could do that, with a main heading, some text, then a sub-heading and some more text:

See the Pen Heading outlines example #1 by Amelia Bellamy-Royds (@AmeliaBR) on CodePen.

Here’s another way to arrange the same headings and paragraphs:

See the Pen Heading outlines example #2 by Amelia Bellamy-Royds (@AmeliaBR) on CodePen.

And here’s a third:

See the Pen Heading outlines example #3 by Amelia Bellamy-Royds (@AmeliaBR) on CodePen.

If you’re only looking at the result tab of those pens, and using your eyes to do so, you might be forgiven for thinking the second and the third are identical, and very different from the first. Visually, both example #2 and example #3 have a main section with a big heading and a sidebar section with a minor heading. The difference is that one uses <div> elements to create the structure and the other uses HTML sectioning elements.

If you’ve read this far, you probably won’t be too surprised to discover that these two examples create different structures when processed by the HTML document outline algorithm. Under that algorithm, divs are ignored, so Example #2 would be treated the exact same as example #1: a main heading, some paragraph text, then a sub-heading and another paragraph. The outline does not indicate at all that the sidebar is a separate, parallel structure to the main article:

In contrast, if I run the outline algorithm on Example #3, It tells me that there is an unlabelled main document (no top-level heading), with two equal sibling child elements (both headings treated as level-2). So now it clearly conveys the parallel structure, but not the difference in heading importance:

I don’t think either of these outlines accurately describes that visual layout. Neither does the outline based on tag names, which not only treats the sidebar as nested in the main article, but also gets distracted by my use of <h6> in a page without any <h2/3/4/5> elements.

If I was asked to describe this layout to someone, I would tell them two things:

• there are two, side-by-side sections;
• one of those sections is more important than the other.

The relative importance of the components is a separate piece of information from the nesting structure—or lack thereof, in this simple example. In a more complex example, you’ll have some chunks of content with meaningful nested headings (like this article), and other chunks (like the sidebars, or the comment section below) that have parallel, independent outlines whose inner heading levels are un-related to the ones in the first chunk. Treating each parallel chunk as equal ignores the relative importance they were given in the markup. But tacking those extra headings onto the end of the main article, just because there isn’t a bigger heading in between, seems somehow worse.

Even when components are nested, they often have an importance level that is independent of the number of sections that surround them. I write books on SVG for O’Reilly. The markup we use to create the books is converted to HTML. The book (level-1 heading) has chapters (level-2 headings) with sections (level-3 headings) that sometimes have sub-sections or even sub-sub-sections (level-4 and 5). But it also has examples, and warning notes, and sidebars, all of which can have their own headings which will be styled identically irrespective of whether that component is in a regular section or a sub-sub-section. If we used the “correct” HTML heading elements, they would have different tag names, depending on the section depth, but would be styled identically.

In web design and in content management, we have two very different ways of talking about the level of a heading: the level of importance, or the level of nesting. I think that the main reason web standards folks can’t agree on an algorithm for turning headings into an outline is because people want an algorithm in which both agree, and they often don’t.

Maybe what’s really needed is to stop talking about outlines as if they re-number heading importance levels. Stop telling web developers they are wrong for using the heading levels that make sense for their content. Let context define the outline nesting, but don’t define outline nesting as if it was interchangeable with tag names. Ideally, find a way for browsers to communicate to screen readers both the nested structure of sections and the raw heading-level numbers, so the screen readers can let their users navigate by nesting structure, while still communicating the relative importance of each heading.

Then focus on the real question:

How can we summarize the meaningful structure of a web page, so that people using assistive technology can easily find content?

My instinct is that the outline that uses sectioning elements is usually better for navigation than sections based only on tag names, but that the details need to be improved. In particular:

• There need to be better rules for collapsing un-named sections, maybe treating them as ARIA groups instead of as additional nesting levels in the outline.
• There may need to be better rules for handling multi-part headings grouped by an <hgroup> or <header> element.
• And there probably need to be better rules about which elements (if any) encapsulate their child headings from the main outline altogether.

Show Me the Data

But that’s just my opinion.

In order to get browsers or screen-readers to change their behavior—let alone to convince all the hundreds of thousands of web developers who are using headings in their content—we are going to need more than hunches and opinions. As I argued early on, we need some data. Both Jake and Brian have echoed that call.

But the kind of data we need isn’t the kind that can be collected by a web crawler. We need data about meaning, the kind of meaning that only real human brains can provide.

The HTML sectioning elements have been around for years now. They aren’t theoretical anymore. They are part of the language that you, web developers, use to communicate. If you’re using sectioning elements, hopefully you have a reason why. When you select a heading tag, hopefully you have a reason why. It’s time to review the HTML standards to make sure they reflect the reasons and meaning used by most developers.

So, I’m asking you: run your favorite websites (that you built or that you use) through the two outline builders in the HTML validator.

• Do either of the outlines make sense?
• Can you make them make sense, with reasonable tweaks to the markup that you can implement with your build systems or component frameworks?
• Which outline is better?
• What aspects of the document structure cause the most problems?

And while we’re at it, one more question:

How would you, as a web user, like to be able to access and navigate documents based on headings or outlines?

The Document Outline Dilemma is a post from CSS-Tricks

Post pobrano z: Annotation is Now a Web Standard

This sure is exciting news: the various groups that make up the W3C have agreed upon a set of rules by which we’ll be able to annotate, highlight and make comments to a webpage without the need of a third party script or framework.

Dan Whaley describes why this could be a big deal:

The W3C standards are a key milestone towards a future in which all pages could support rich layers of conversation without requiring any action by their publishers—because that capability can be built into the browser itself and be available as a native feature, just like like web search. The shared vision is that conversations will be able happen anywhere on the Web, or even on documents in native apps, and inline instead of below-the fold, in a federated, standards-based way.

Direct Link to Article — Permalink

Annotation is Now a Web Standard is a post from CSS-Tricks

Post pobrano z: PHAEDIS

Post pobrano z: West Elm Hotels

Post pobrano z: Bang & Olufsen

Post pobrano z: Computer Science Distilled, Chapter 2: Complexity

In almost every computation, a variety of arrangements for the processes is possible. It is essential to choose that arrangement which shall tend to minimize the time necessary for the calculation.

—Ada Lovelace

How much time does it take to sort 26 shuffled cards? If instead, you had 52 cards, would it take twice as long? How much longer would it take for a thousand decks of cards? The answer is intrinsic to the method used to sort the cards.

A method is a list of unambiguous instructions for achieving a goal. A method that always requires a finite series of operations is called an algorithm. For instance, a card-sorting algorithm is a method that will always specify some operations to sort a deck of 26 cards per suit and per rank.

Less operations need less computing power. We like fast solutions, so we monitor the number of operations in our algorithms. Many algorithms require a fast-growing number of operations when the input grows in size. For example, our card-sorting algorithm could take few operations to sort 26 cards, but four times more operations to sort 52 cards!

To avoid bad surprises when our problem size grows, we find the algorithm’s time complexity. In this chapter, you’ll learn to:

• Count and interpret time complexities
• Express their growth with fancy Big-O’s
• Run away from exponential algorithms
• Make sure you have enough computer memory.

But first, how do we define time complexity?

Time complexity is written T⁢(n). It gives the number of operations the algorithm performs when processing an input of size n. We also refer to an algorithm’s T⁢(n) as its running cost. If our card-sorting algorithm follows T⁢(n)=n2, we can predict how much longer it takes to sort a deck once we double its size: T⁢(2⁢n)T⁢(n)=4.

Hope for the best, prepare for the worst

Isn’t it faster to sort a pile of cards that’s almost sorted already?

Input size isn’t the only characteristic that impacts the number of operations required by an algorithm. When an algorithm can have different values of T⁢(n) for the same value of n, we resort to cases:

• Best Case: when the input requires the minimum number of operations for any input of that size. In sorting, it happens when the input is already sorted.
• Worst Case: when the input requires the maximum number of operations for any input of that size. In many sorting algorithms, that’s when the input was given in reverse order.
• Average Case: refers to the average number of operations required for typical inputs of that size. For sorting, an input in random order is usually considered.

In general, the most important is the worst case. From there, you get a guaranteed baseline you can always count on. When nothing is said about the scenario, the worst case is assumed. Next, we’ll see how to analyze a worst case scenario, hands on.

2.1 Counting Time

We find the time complexity of an algorithm by counting the number of basic operations it requires for a hypothetical input of size n. We’ll demonstrate it with Selection Sort, a sorting algorithm that uses a nested loop. An outer for loop updates the current position being sorted, and an inner for loop selects the item that goes in the current position¹:

function selection_sort(list)
    for current ← 1 … list.length - 1
        smallest ← current
        for i ← current + 1 … list.length
            if list[i] < list[smallest]
                smallest ← i
        list.swap_items(current, smallest)

Let’s see what happens with a list of n items, assuming
the worst case. The outer loop runs n-1 times and does two
operations per run (one assignment and one swap) totaling 2⁢n-2 operations. The inner loop first runs n-1 times, then n-2 times, n-3 times, and so on. We know how to sum these types of sequences²:

In the worst case, the if condition is always met. This means the inner loop does one comparison and one assignment (n2-n)/2 times, hence n2-n operations. In total, the algorithm costs 2⁢n-2 operations for the outer loop, plus n2-n operations for the inner loop. We thus get the time complexity:

Now what? If our list size was n=8 and we double it, the
sorting time will be multiplied by:

If we double it again we will multiply time by 3.90. Double it over and over and find 3.94, 3.97, 3.98. Notice how this gets closer and closer to 4? This means it would take four times as long to sort two million items than to sort one million items.

2.1.1 Understanding Growth

Say the input size of an algorithm is very large, and we increase it even more. To predict how the execution time will grow, we don’t need to know all terms of T⁢(n). We can approximate T⁢(n) by its fastest-growing term, called the dominant term.

The Index Card Problem: Yesterday, you knocked over one box of index cards. It took you two hours of Selection Sort to fix it. Today, you spilled ten boxes. How much time will you need to arrange the cards back in?

We’ve seen Selection Sort follows T⁢(n)=n2+n-2. The fastest-growing term is n2,
therefore we can write T⁢(n)≈n2. Assuming there are n cards per box, we find:

It will take you approximately (100×2)⁢hours=200 hours! What if we had used a different sorting method? For example, there’s one called „Bubble Sort” whose time complexity is T⁢(n)=0.5⁢n2+0.5⁢n. The fastest-growing term then gives T⁢(n)≈0.5⁢n2, hence:

The 0.5 coefficient cancels itself out! The idea that n2-n-2 and 0.5⁢n2+0.5⁢n both grow like n2 isn’t easy to get. How does the fastest-growing term of a function ignore all other numbers and dominate growth? Let’s try to visually understand this.

In Figure 2.2, the two time complexities we’ve seen are compared to n2 at different zoom levels. As we plot them for larger and larger values of n, their curves seem to get closer and closer. Actually, you can plug any numbers into the bullets of T⁢(n)=∙⁢n2+∙⁢n+∙, and it will still grow like n2.

Remember, this effect of curves getting closer works if the fastest-growing term is the same. The plot of a function with a linear growth (n) never gets closer and closer to one with a quadratic growth (n2), which in turn never gets closer and closer to one having a cubic growth (n3).

That’s why with very big inputs, algorithms with a quadratically growing cost perform a lot worse than algorithms with a linear cost. However, they perform a lot better than those with a cubic cost. If you’ve understood this, the next section will be easy: we will just learn the fancy notation coders use to express this.

2.2 The Big-O Notation

There’s a special notation to refer to classes of growth: the Big-O notation. A function with a fastest-growing term of 2n or weaker is O⁢(2n); one with a quadratic or weaker growth is O⁢(n2); growing linearly or less, O⁢(n), and so on. The notation is used for expressing the dominant term of algorithms’ cost functions in the worst case—that’s the standard way of expressing time complexity³.

Both Selection Sort and Bubble Sort are O⁢(n2), but we’ll soon discover O⁢(n⁢log⁡n) algorithms that do the same job. With our O⁢(n2) algorithms, 10× the input size resulted in 100× the running cost. Using a O⁢(n⁢log⁡n) algorithm, 10× the input size results in only 10⁢log⁡10≈34⁢× the running cost.

When n is a million, n2 is a trillion, whereas n⁢log⁡n is just a few million. Years running a quadratic algorithm on a large input could be equivalent to minutes if a O⁢(n⁢log⁡n) algorithm was used. That’s why you need time complexity analysis when you design systems that handle very large inputs.

When designing a computational system, it’s important to anticipate the most frequent operations. Then you can compare the Big-O costs of different algorithms that do these operations⁴. Also, most algorithms only work with specific input structures. If you choose your algorithms in advance, you can structure your input data accordingly.

Some algorithms always run for a constant duration regardless of input size—they’re O⁢(1). For example, checking if a number is odd or even: we see if its last digit is odd and boom, problem
solved. No matter how big the number. We’ll see more O⁢(1) algorithms in the next chapters. They’re amazing, but first let’s see which algorithms are not amazing.

2.3 Exponentials

We say O⁢(2n) algorithms are exponential time. From the graph of growth orders (Figure 2.3), it doesn’t seem the quadratic n2 and the exponential 2n are much different. Zooming out the graph, it’s obvious the exponential growth brutally dominates the quadratic one:

Exponential time grows so much, we consider these algorithms „not runnable”. They run for very few input types, and require huge amounts of computing power if inputs aren’t tiny. Optimizing every aspect of the code or using supercomputers doesn’t help. The crushing exponential always dominates growth and keeps these algorithms unviable.

To illustrate the explosiveness of exponential growth, let’s zoom out the graph even more and change the numbers (Figure 2.5). The exponential was reduced in power (from 2 to 1.5) and had its growth divided by a thousand. The polynomial had its exponent increased (from 2 to 3) and its growth multiplied by a thousand.

Some algorithms are even worse than exponential time algorithms. It’s the case of factorial time algorithms, whose time complexities are O⁢(n!). Exponential and factorial time algorithms are horrible, but we need them for the hardest computational problems: the famous NP-complete problems. We will see important examples of NP-complete problems in the next chapter. For now, remember this: the first person to find a non-exponential algorithm to a NP-complete problem gets a million dollars⁵ from the Clay Mathematics Institute.

It’s important to recognize the class of problem you’re dealing with. If it’s known to be NP-complete, trying to find an optimal solution is fighting the impossible. Unless you’re shooting for that million dollars.

2.4 Counting Memory

Even if we could perform operations infinitely fast, there would still be a limit to our computing power. During execution, algorithms need working storage to keep track of their ongoing calculations. This consumes computer memory, which is not infinite.

The measure for the working storage an algorithm needs is called space complexity. Space complexity analysis is similar to time complexity analysis. The difference is that we count computer memory, and not computing operations. We observe how space complexity evolves when the algorithm’s input size grows, just as we do for time complexity.

For example, Selection Sort just needs working storage for a fixed set of variables. The number of variables does not depend on the input size. Therefore, we say Selection Sort’s space complexity is O⁢(1): no matter what the input size, it requires the same amount of computer memory for working storage.

However, many other algorithms need working storage that grows with input size. Sometimes, it’s impossible to meet an algorithm’s memory requirements. You won’t find an appropriate sorting algorithm with O⁢(n⁢log⁡n) time complexity and O⁢(1) space complexity. Computer memory limitations sometimes force a tradeoff. With low memory, you’ll probably need an algorithm with slow O⁢(n2) time complexity because it has O⁢(1)
space complexity.

Conclusion

In this chapter, we learned algorithms can have different types of voracity for consuming computing time and computer memory. We’ve seen how to assess it with time and space complexity analysis. We learned to calculate time complexity by finding the exact T⁢(n) function, the number of operations performed by an algorithm.

We’ve seen how to express time complexity using the Big-O notation (O). Throughout this book, we’ll perform simple time complexity analysis of algorithms using this notation. Many times, calculating T⁢(n) is not necessary for inferring the Big-O complexity of an algorithm.

We’ve seen the cost of running exponential algorithms explode in a way that makes these algorithms not runnable for big inputs. And we learned how to answer these questions:

• Given different algorithms, do they have a significant difference in terms of operations required to run?
• Multiplying the input size by a constant, what happens with the time an algorithm takes to run?
• Would an algorithm perform a reasonable number of operations once the size of the input grows?
• If an algorithm is too slow for running on an input of a given size, would optimizing the algorithm, or using a supercomputer help?

¹: To understand an new algorithm, run it on paper with a small sample input.

²: In the previous chapter, we showed ∑i=1ni=n⁢(n+1)/2.

³: We say ’oh’, e.g., „that sorting algorithm is oh-n-squared„.

⁴: For the Big-O complexities of most algorithms that do common tasks, see http://code.energy/bigo

⁵: It has been proven a non-exponential algorithm for any NP-complete problem could be generalized to all NP-complete problems. Since we don’t know if such an algorithm exists, you also get a million dollars if you prove an NP-complete problem cannot be solved by non-exponential algorithms!

Computer Science Distilled: Learn the Art of Solving Computational Problems by Wladston Viana Ferreira Filho is available on Amazon now.

Computer Science Distilled, Chapter 2: Complexity is a post from CSS-Tricks

Post pobrano z: Websites to Generate SVG Patterns

These aren’t particularly hard to web search for, but just in case you didn’t know they existed I figured I’d drop them here. I’ve used all three of these in the past and I think they do a good job of driving home how cool of patterns you can make in SVG with such little code.

Hero Patterns

A collection of repeatable SVG background patterns for you to use on your web projects.

SVG Patterns Gallery

SVG images are typically smaller than bitmap images and remain sharp on high-dpi screens. Unlike CSS3 gradients, SVG images are supported on IE9.

SVGeneration

Scalable Vector Graphics are crisp and clear and can be rendered in all modern browsers.

Websites to Generate SVG Patterns is a post from CSS-Tricks